[P4886] 快递员
程序员文章站
2022-11-10 22:30:27
考虑在树上选个点rt作为根,并且快递中心就选这儿。计算出所有配送的代价(2 两段之和),设他们的最大值为Max。若此时存在下列情况时,可以判定Max已经为最优解。 1)存在代价为Max的配送(u,v)且uv分别属于rt的不同的两个“儿子的子树”。 2)存在代价为Max的配送(u1,v1)(u2,v2 ......
考虑在树上选个点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("%d\n",solveat(rt)); return 0; }