OJ题号：BZOJ4890、洛谷3761
思路：
总共有$n$个结点、$n-1$条边，说明整个图是一个无根树。
枚举每一条边$w$，并计算删除这条边以后的最大费用。
首先我自己定义了两个概念：
树的中心：树上的一点，保证从该点出发的最长简单路最短。
树的半径：从树的中心出发的最长简单路。
每次删边时会把整棵树分成两个不相交的新树。
对于每棵新树，可以分别求出它们的直径$d1$ $d2$、中心及半径$r1$ $r2$。则最优化修改该边后所能获得的最大费用为$max(d1,d2,r1+r2+w)$。
受到周欣的启发，有了以下的一个优化：先求出整棵树的直径，则需要删除的边一定在直径上。
证明：如果修改的边不在直径上，那么修改改边后，直径仍然存在，则对于该边的修改没有意义。
周欣提出的另一个比较有用但是没有被我采用的优化：特判链的情况。
1 #include<cstdio> 2 #include<algorithm> 3 #include<vector> 4 #include<cctype> 5 inline int getint() { 6 char ch; 7 while(!isdigit(ch=getchar())); 8 int x=ch^'0'; 9 while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0'); 10 return x; 11 } 12 const int N=6000,inf=0x7fffffff; 13 struct Edge { 14 int to,w; 15 }; 16 int n; 17 std::vector<Edge> e[N]; 18 int uu=0,vv=0,stop=0; 19 int v,w,d,y,u; 20 void find_vertex(int x,int depth,int parent) { 21 if(depth>d) { 22 d=depth; 23 v=x; 24 } 25 for(register unsigned int i=0;i<e[x].size();i++) { 26 if((e[x][i].to!=parent)&&(e[x][i].to!=uu)&&(e[x][i].to!=vv)) { 27 find_vertex(e[x][i].to,depth+e[x][i].w,x); 28 } 29 } 30 } 31 void find_d(int x,int depth,int parent) { 32 if(depth>y) { 33 y=depth; 34 u=x; 35 } 36 for(unsigned int i=0;i<e[x].size();i++) { 37 if((e[x][i].to!=parent)&&(e[x][i].to!=stop)) { 38 find_d(e[x][i].to,depth+e[x][i].w,x); 39 } 40 } 41 } 42 int l[N]; 43 bool find_path(int x,int depth,int parent) { 44 w++; 45 l[w]=depth; 46 if(x==u) return true; 47 for(register unsigned int i=0;i<e[x].size();i++) { 48 if(e[x][i].to!=parent) { 49 if(find_path(e[x][i].to,depth+e[x][i].w,x)) return true; 50 } 51 } 52 w--; 53 return false; 54 } 55 inline int find_mid() { 56 for(int i=0;i<w;i++) { 57 if((l[i]<=(y>>1))&&(l[i+1]>=(y>>1))) { 58 return std::min(std::max(l[i],y-l[i]),std::max(l[i+1],y-l[i+1])); 59 } 60 } 61 return 0; 62 } 63 inline int getsum(int p) { 64 w=0,d=0,y=0,v=p; 65 find_vertex(p,0,0); 66 find_d(v,0,0); 67 find_path(v,0,0); 68 return find_mid(); 69 } 70 struct Edge2 { 71 int from,to,w; 72 }; 73 Edge2 p[N]; 74 int w_whole; 75 bool find_path_whole(int x,int parent,int w) { 76 p[w_whole]=(Edge2){parent,x,w}; 77 w_whole++; 78 if(x==u) return true; 79 for(register unsigned int i=0;i<e[x].size();i++) { 80 if(e[x][i].to!=parent) { 81 if(find_path_whole(e[x][i].to,x,e[x][i].w)) return true; 82 } 83 } 84 w_whole--; 85 return false; 86 } 87 int main() { 88 n=getint(); 89 for(int i=1;i<n;i++) { 90 u=getint(),v=getint(),w=getint(); 91 e[u].push_back((Edge){v,w}); 92 e[v].push_back((Edge){u,w}); 93 } 94 w_whole=0,d=0,y=0; 95 find_vertex(1,0,0); 96 find_d(v,0,0); 97 find_path_whole(v,0,0); 98 int ans=inf; 99 for(register int i=1;i<w_whole;i++) { 100 uu=p[i].from; 101 vv=p[i].to; 102 int s1,s2,cmp=0; 103 stop=vv; 104 s1=getsum(uu); 105 cmp=std::max(cmp,y); 106 stop=uu; 107 s2=getsum(vv); 108 cmp=std::max(cmp,y); 109 ans=std::min(ans,std::max(s1+p[i].w+s2,cmp)); 110 } 111 printf("%d ",ans); 112 return 0; 113 }