题目链接：重建计划
这道题现在已经成为一道板子题了……
这是个非常显然的0-1分数规划，可以二分答案之后树分治判定一下。注意树分治的时候如果使用单调队列，需要把所有儿子预先按最大深度排好序，否则会被扫把型的数据卡到(n^2log n)。
然后跑得非常慢……于是把二分答案改成了Dinkelbach迭代法。Dinkelbach迭代法就是每次用当前最优解来更新答案的界，跑得比香港记者还快
听说这玩意儿复杂度上界是(log)级别的？然而我并不会证……感觉这玩意儿就是玄学啊……
二分答案代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
#define maxn 100010
#define INF 2147483647
#define eps 1e-6
using namespace std;
typedef long long llg;
int n,L,R,siz[maxn],dx[maxn],lc,dep[maxn];
int fr[maxn<<1],a[maxn],la,d[maxn],ld,s[maxn];
int head[maxn],next[maxn<<1],to[maxn<<1],tt;
double c[maxn<<1],lt,dis[maxn];
double c1[maxn],c2[maxn],ans;
bool vis[maxn];
int getint(){
int w=0;bool q=0;
char c=getchar();
while((c>'9'||c<'0')&&c!='-') c=getchar();
if(c=='-') c=getchar(),q=1;
while(c>='0'&&c<='9') w=w*10+c-'0',c=getchar();
return q?-w:w;
}
bool cmp(int x,int y){return dep[to[x]]<dep[to[y]];}
void link(int x,int y,int z){
to[++tt]=y;next[tt]=head[x];
head[x]=tt; c[tt]=z;
}
void dfs(int u,int x){
siz[u]=1; dx[u]=0; dep[u]=x;
d[++ld]=u; vis[u]=1;
for(int i=head[u],v;v=to[i],i;i=next[i])
if(!vis[v]){
dfs(v,x+1); siz[u]+=siz[v];
dx[u]=max(dx[u],siz[v]);
dep[u]=max(dep[u],dep[v]);
}
vis[u]=0;
}
void getroot(int u,int fa){
ld=0; dfs(u,0); int k=0,_k=INF;
for(int l=1,i;i=d[l],l<=ld;l++){
dx[i]=max(dx[i],siz[u]-siz[i]);
if(dx[i]<_k) k=i,_k=dx[i];
}
vis[k]=1; fr[fa]=k;
for(int i=head[k];i;i=next[i])
if(!vis[to[i]]) getroot(to[i],i);
ld=0; dfs(k,0); vis[k]=0; la=0;
for(int i=head[k];i;i=next[i]) a[++la]=i;
sort(a+1,a+la+1,cmp); next[a[la]]=0; head[k]=a[1];
for(int i=1;i<la;i++) next[a[i]]=a[i+1];
}
void getdis(int u,int de){
vis[u]=1; lc=max(lc,de); c2[de]=max(c2[de],dis[u]);
for(int i=head[u],v;v=to[i],i;i=next[i])
if(!vis[v]) dis[v]=dis[u]+c[i],getdis(v,de+1);
vis[u]=0;
}
void work(int u,int fa){
int k=fr[fa]; vis[k]=1; int cl=0;
for(int i=head[k],v,l,r,no;v=to[i],i;i=next[i]){
if(vis[v]) continue; lc=0;
dis[v]=c[i]; getdis(v,1); l=r=0; no=0;
for(int j=lc;j;j--){
while(no<=R-j && no<=cl){
while(l<r && c1[s[r-1]]<=c1[no]) r--;
s[r++]=no++;
}
while(l<r && s[l]<L-j) l++;
if(l<r) ans=max(ans,c2[j]+c1[s[l]]);
if(ans+eps>=0) break;
}
cl=max(cl,lc);
for(int j=1;j<=lc;j++) c1[j]=max(c1[j],c2[j]),c2[j]=-1e9;
}
for(int i=1;i<=cl;i++) c1[i]=-1e9;
if(ans+eps>=0){vis[k]=0;return;}
for(int i=head[k];i;i=next[i])
if(!vis[to[i]]) work(to[i],i);
vis[k]=0;
}
bool check(double x){
for(int i=1;i<=tt;i++) c[i]+=lt-x; lt=x;
ans=-1e9; work(1,0); return ans+eps>=0;
}
int main(){
File("a");
n=getint(),L=getint(),R=getint();
for(int i=2,u,v;i<=n;i++){
u=getint(),v=getint();
to[++tt]=v;next[tt]=head[u];head[u]=tt;
to[++tt]=u;next[tt]=head[v];head[v]=tt;
c[tt-1]=c[tt]=getint();
}
getroot(1,0);
for(int i=1;i<=n;i++) c1[i]=c2[i]=-1e9;
double l=0,r=1000000,mid;
while(r-l>=1e-4){
mid=(l+r)*0.5;
if(check(mid)) l=mid;
else r=mid;
}
printf("%.3lf",l);
return 0;
}
Dinkelbach迭代法代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
#define maxn 100010
#define INF 2147483647
using namespace std;
typedef long long llg;
int n,L,R,siz[maxn],dx[maxn],lc,dep[maxn];
int fr[maxn<<1],a[maxn],la,d[maxn],ld,s[maxn];
int head[maxn],next[maxn<<1],to[maxn<<1],tt;
double c[maxn<<1],lt,dis[maxn];
double c1[maxn],c2[maxn],ans;
bool vis[maxn];
int getint(){
int w=0;bool q=0;
char c=getchar();
while((c>'9'||c<'0')&&c!='-') c=getchar();
if(c=='-') c=getchar(),q=1;
while(c>='0'&&c<='9') w=w*10+c-'0',c=getchar();
return q?-w:w;
}
bool cmp(int x,int y){return dep[to[x]]<dep[to[y]];}
void link(int x,int y,int z){
to[++tt]=y;next[tt]=head[x];
head[x]=tt; c[tt]=z;
}
void dfs(int u,int x){
siz[u]=1; dx[u]=0; dep[u]=x;
d[++ld]=u; vis[u]=1;
for(int i=head[u],v;v=to[i],i;i=next[i])
if(!vis[v]){
dfs(v,x+1); siz[u]+=siz[v];
dx[u]=max(dx[u],siz[v]);
dep[u]=max(dep[u],dep[v]);
}
vis[u]=0;
}
void getroot(int u,int fa){
ld=0; dfs(u,0); int k=0,_k=INF;
for(int l=1,i;i=d[l],l<=ld;l++){
dx[i]=max(dx[i],siz[u]-siz[i]);
if(dx[i]<_k) k=i,_k=dx[i];
}
vis[k]=1; fr[fa]=k;
for(int i=head[k];i;i=next[i])
if(!vis[to[i]]) getroot(to[i],i);
ld=0; dfs(k,0); vis[k]=0; la=0;
for(int i=head[k];i;i=next[i]) a[++la]=i;
sort(a+1,a+la+1,cmp); next[a[la]]=0; head[k]=a[1];
for(int i=1;i<la;i++) next[a[i]]=a[i+1];
}
void getdis(int u,int de){
vis[u]=1; lc=max(lc,de); c2[de]=max(c2[de],dis[u]);
for(int i=head[u],v;v=to[i],i;i=next[i])
if(!vis[v]) dis[v]=dis[u]+c[i],getdis(v,de+1);
vis[u]=0;
}
void work(int u,int fa){
int k=fr[fa]; vis[k]=1; int cl=0; double x;
for(int i=head[k],v,l,r,no;v=to[i],i;i=next[i]){
if(vis[v]) continue; lc=0;
dis[v]=c[i]; getdis(v,1); l=r=0; no=0;
for(int j=lc;j;j--){
while(no<=R-j && no<=cl){
while(l<r && c1[s[r-1]]<=c1[no]) r--;
s[r++]=no++;
}
while(l<r && s[l]<L-j) l++;
if(l<r){
x=(c2[j]+c1[s[l]])/(j+s[l]);
if(x>ans) ans=x;
}
}
cl=max(cl,lc);
for(int j=1;j<=lc;j++) c1[j]=max(c1[j],c2[j]),c2[j]=-1e9;
}
for(int i=1;i<=cl;i++) c1[i]=-1e9;
for(int i=head[k];i;i=next[i])
if(!vis[to[i]]) work(to[i],i);
vis[k]=0;
}
void check(double x){
for(int i=1;i<=tt;i++) c[i]+=lt-x; lt=x;
ans=-1e9; work(1,0);
}
int main(){
File("a");
n=getint(),L=getint(),R=getint();
for(int i=2,u,v;i<=n;i++){
u=getint(),v=getint();
to[++tt]=v;next[tt]=head[u];head[u]=tt;
to[++tt]=u;next[tt]=head[v];head[v]=tt;
c[tt-1]=c[tt]=getint();
}
getroot(1,0);
for(int i=1;i<=n;i++) c1[i]=c2[i]=-1e9;
double now=0; check(0);
while(ans>1e-4) now+=ans,check(now);
printf("%.3lf",now);
return 0;
}
实测BZOJ上前一份代码24s+，后一份代码只要5s+