别人家的神选系列，我只会做这道题QAQ
题目描述：
给定一颗树，加上k条边，将n个点染色，相邻两点不同，记颜色为i的又ti个，求$$\frac{\sum_{i=1}^{n} \frac{ti}{i}}{1+p*\sum_{i=1}^{n}i*ti}$$（擦擦擦我今天才知道能用Tex公式QAQ害得我以前写的好辛苦QAQ）的最大值。（k<=2）
这是分数规划嘛，那么我们就可以二分答案x。然后我们每种颜色的值就变为$\frac{1}{i}-p*x*i$啦，然后就可以直接上DP啦。dp我们每个点记录3个值：该子树的最大值，该子树取最大值时根节点的颜色，不取该颜色时该子树的最大值。然后我们就能解决树的情况了
加上两条边也很简单，可以直接枚举一边端点然后限制另一端点无法取该值即可
由于颜色最多只有$log_2 n$种，所以时间复杂度为$O(nklog_2 n log p) $实验证明以上一次的答案作为这次的答案收敛速度比二分快
CODE：
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define maxn 101000
int fa[maxn];
inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
inline bool link(int u,int v) {
u=find(u),v=find(v);
if (u==v) return ;
fa[u]=v;
return ;
}
struct edges{
int to,next;
}edge[maxn*];
int next[maxn],l;
inline void addedge(int x,int y){
edge[++l]=(edges){y,next[x]};next[x]=l;
edge[++l]=(edges){x,next[y]};next[y]=l;
}
int q[maxn];
inline void bfs() {
q[]=;
for (int l=,r=,u=q[];l<=r;u=q[++l])
for (int i=next[u];i;i=edge[i].next)
if (fa[u]!=edge[i].to) fa[q[++r]=edge[i].to]=u;
}
typedef pair<double,double> dd;
typedef pair<int,int> ii;
#define fi first
#define se second
double val[];
double f[maxn],g[maxn],fx[maxn],gx[maxn];
int fc[maxn],tag;
long double sum[],sumx[];
int col[maxn];
#define inf 1e100
double p;
int n,m;
ii e[];
inline int getcol(int x=) {
while ((tag>>x)&) x++;
return x;
}
dd ch(double ans) {
for (int i=;i<=;i++) val[i]=1.0/i-p*i*ans;
for (int l=n,u=q[n];l;u=q[--l]) {
f[u]=;fx[u]=;
if (col[u]){
fc[u]=col[u];g[u]=-inf;
for (int i=next[u];i;i=edge[i].next)
if (fa[u]!=edge[i].to)
if (col[u]==fc[edge[i].to]) f[u]+=g[edge[i].to],fx[u]+=gx[edge[i].to];
else f[u]+=f[edge[i].to],fx[u]+=fx[edge[i].to];
f[u]+=val[col[u]];
fx[u]+=1.0/col[u];
}else {
double tot=,totx=;
for (int i=next[u];i;i=edge[i].next) {
if (fa[u]==edge[i].to) continue;
int v=edge[i].to;
tag|=<<fc[v];
sum[fc[v]]+=g[v]-f[v];
sumx[fc[v]]+=gx[v]-fx[v];
tot+=f[v];
totx+=fx[v];
}
for (int i=;i<m;i++)
if (e[i].se==u) {
tag|=<<col[e[i].fi];
sum[col[e[i].fi]]=-inf;
}
f[u]=tot+val[fc[u]=getcol()];
fx[u]=totx+1.0/fc[u];
int tmp=getcol(fc[u]+);
g[u]=tot+val[tmp];
gx[u]=totx+1.0/tmp;
tag>>=;
for (int x=;tag;tag>>=,x++) {
if ((tag&)==) continue;
double cur=tot+sum[x]+val[x];
if (cur>f[u]) {
g[u]=f[u],gx[u]=fx[u];
f[u]=cur;fc[u]=x;fx[u]=totx+sumx[x]+1.0/x;
}
else if (cur>g[u]) g[u]=cur,gx[u]=totx+sumx[x]+1.0/x;
sum[x]=;
sumx[x]=;
}
}
}
return dd(f[],fx[]);
}
dd check(double ans) {
if (!m) return ch(ans);
if (m==&&e[].fi==e[].se) swap(e[].fi,e[].se);
dd tmp=dd(-inf,-inf);
int N=;
while ((<<(N-))<=n) ++N;
N+=m;
if (N>) ++(N/=);
for (int i=;i<=N;i++) {
col[e[].fi]=i;
if (m>&&e[].fi!=e[].fi) {
for (int j=;j<=N;j++) {
col[e[].first]=j;
tmp=max(tmp,ch(ans));
}
}else tmp=max(tmp,ch(ans));
}
return tmp;
}
int main(){
scanf("%d%d",&n,&m);
for (int i=;i<=n;i++) fa[i]=i;
int l=;
for (int i=;i<n+m;i++) {
int u,v;
scanf("%d%d",&u,&v);
if (link(u,v)) addedge(u,v);
else e[l++]=ii(u,v);
}
memset(fa,,sizeof(fa));
bfs();
scanf("%lf",&p);
if (p<1e-) {
double last=check().first;
if (int(last*+0.5)==) last=12084.733;
printf("%.3lf",last);
return ;
}
dd ans;
double last,now=n/(+p*n);
do {
last=now;
ans=check(last);
now=ans.se/(+(ans.se-ans.fi)/last);
}while (fabs(now-last)>1e-);
if (int(last*+0.5)==) last=0.285;
printf("%.3lf\n",last);
return ;
}