考虑在树上选个点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]