c/c++语言开发共享[P4886] 快递员

考虑在树上选个点rt作为根，并且快递中心就选这儿。计算出所有配送的代价（2*两段之和），设他们的最大值为max。若此时存在下列情况时，可以判定max已经为最优解。

1）存在代价为max的配送(u,v)且uv分别属于rt的不同的两个“儿子的子树”。
2）存在代价为max的配送(u1,v1)(u2,v2)且u1u2分别属于rt的不同的两个“儿子的子树”。
3）存在代价为max的配送(u1,v1)(u2,v2)且v1v2分别属于rt的不同的两个“儿子的子树”。

但是若1）不存在，2）、3）不就是一种情况了吗，滑稽。 概括一下就是当所欲代价为max的配送的端点所属于的“儿子的子树”不唯一，则已达到最优解，证明就上边那三种情况。

如果都不满足的话，那么更优的选点应在max的配送(u,v)的u（=v）所属于的那个“儿子的子树”里。分治下去就好。

【实现】

int n,m; int head[n],to[m],len[m],last[m]; int sum,rt,qu[n],qv[n],fiz[n],siz[n],dis[n],bel[n]; bool ban[n];  void addedge(int x,int y,int w) {     static int cnt=0;     to[++cnt]=y;     len[cnt]=w;     last[cnt]=head[x];     head[x]=cnt; } void getroot(int x,int pa) {     fiz[x]=0,siz[x]=1;     for(int i=head[x]; i; i=last[i]) {         if(to[i]==pa||ban[to[i]]) continue;         getroot(to[i],x);         siz[x]+=siz[to[i]];         fiz[x]=max(fiz[x],siz[to[i]]);      }     fiz[x]=max(fiz[x],sum-siz[x]);     if(fiz[x]<fiz[rt]) rt=x;  } void getdis(int x,int pa,int id) {     bel[x]=id;     for(int i=head[x]; i; i=last[i]) {         if(to[i]==pa) continue;         dis[to[i]]=dis[x]+len[i];         getdis(to[i],x,id);     } } int sta[n]; int solveat(int x) {     if(ban[x]) return 2e9;     ban[x]=1,dis[x]=0;     for(int i=head[x]; i; i=last[i]) {         dis[to[i]]=len[i];         getdis(to[i],x,to[i]);     }     int max=0,top=0;     for(int i=1; i<=m; ++i) {         if(max<dis[qu[i]]+dis[qv[i]]) {             max=dis[qu[i]]+dis[qv[i]];             sta[top=1]=i;         } else if(max==dis[qu[i]]+dis[qv[i]]) {             sta[++top]=i;         }     }     for(int i=1; i<=top; ++i) {         if(bel[qu[sta[i]]]!=bel[qv[sta[i]]]) return max;         if(bel[qu[sta[i]]]!=bel[qu[sta[1]]]) return max;     }     rt=0;     sum=siz[bel[qu[sta[1]]]];     getroot(bel[qu[sta[1]]],x);     return min(max,solveat(rt)); }  int main() {     read(n),read(m);     for(int x,y,w,i=n; --i; ) {         read(x),read(y),read(w);         addedge(x,y,w);         addedge(y,x,w);     }     for(int i=1; i<=m; ++i) {         read(qu[i]),read(qv[i]);     }     sum=n; //写成sum=0疯狂t     fiz[0]=2e9;     getroot(1,0);     printf("%dn",solveat(rt));     return 0; }