题意：给你一棵树，每条边都有值W，然后问你去掉一条边，令val = w*max(两颗新树的直径)，求val最小值~
做法，先求树的直径，然后算出直径上每个点的最长枝条长度。这样对于每一条边，假如是枝条边,那么val = w*直径，如果不是那么val = max(w*(两颗新树的直径))。新树直径说到这里已经很好算了。
DFS爆栈了一下午
1 #include <stdio.h> 2 #include <string.h> 3 #include <iostream> 4 #include <algorithm> 5 #include <stdlib.h> 6 #include <vector> 7 #include <queue> 8 #include <stack> 9 #define loop(s,i,n) for(i = s;i < n;i++) 10 #define cl(a,b) memset(a,b,sizeof(a)) 11 #pragma comment(linker, "/STACK:1024000000,1024000000") 12 const int maxn = 100005; 13 using namespace std; 14 struct edge 15 { 16 int u,v,w,next; 17 }edges[2*maxn]; 18 struct node 19 { 20 int step,u,v; 21 }q[maxn*2]; 22 int maxp,cnt,n; 23 bool vis[maxn],is_on[maxn]; 24 int set[maxn],head[maxn],dep[maxn],rdp[maxn],trans[maxn],rtrans[maxn],rp[maxn],lp[maxn]; 25 26 void init() 27 { 28 int i; 29 for(i = 0;i <= n;i++) 30 vis[i] = 0,head[i] = -1,is_on[i] = 0,rdp[i] = 0; 31 cnt = maxp= 0; 32 dep[0] = -1; 33 } 34 void addedge(int u,int v,int w) 35 { 36 int i; 37 edges[cnt].u = u; 38 edges[cnt].v = v; 39 edges[cnt].w = w; 40 edges[cnt].next = head[u]; 41 head[u] = cnt; 42 cnt++; 43 } 44 void dfs(int u,int deep,int pre) 45 { 46 set[u] = pre; 47 vis[u] = true; 48 dep[u] = deep; 49 if(dep[maxp] < dep[u]) 50 maxp = u; 51 // printf("*****u*** %d *** ",u); 52 int i; 53 for(i = head[u];i != -1;i = edges[i].next) 54 { 55 int v; 56 v = edges[i].v; 57 if(vis[v] == false) 58 { 59 dfs(v,deep+1,u); 60 } 61 } 62 } 63 void bfs(int s) 64 { 65 int i; 66 int maxs = 0; 67 int r,f; 68 f = r = 0; 69 struct node st; 70 st.u = s; 71 st.step = 0; 72 set[s] = -1; 73 q[r++] = st; 74 vis[s] = 1; 75 while(f < r) 76 { 77 struct node tmp; 78 tmp = q[f]; 79 f++; 80 int i; 81 for(i = head[tmp.u];i != -1;i = edges[i].next) 82 { 83 int v; 84 v = edges[i].v; 85 if(!vis[v]) 86 { 87 struct node t; 88 t.u = v; 89 t.step = tmp.step+1; 90 if(maxs < t.step) 91 maxp = v,maxs = t.step; 92 vis[v] = true; 93 set[v] = tmp.u; 94 dep[v] = t.step; 95 q[r++] = t; 96 } 97 } 98 } 99 } 100 int main() 101 { 102 int t,icase; 103 //freopen("data.txt","r",stdin); 104 //freopen("data1.txt","w",stdout); 105 scanf("%d",&t); 106 icase = 0; 107 while(t--) 108 { 109 // int n; 110 int i,j,u,v,w; 111 printf("Case #%d: ",++icase); 112 scanf("%d",&n); 113 init(); 114 loop(0,i,n-1) 115 { 116 scanf("%d %d %d",&u,&v,&w); 117 addedge(u,v,w); 118 addedge(v,u,w); 119 } 120 121 // dfs(1,0,-1); 122 bfs(1); 123 124 for(i = 0;i <= n;i++) 125 vis[i] = false; 126 int tmp; 127 tmp = maxp; 128 maxp = 0; 129 //dfs(tmp,0,-1); 130 bfs(tmp); 131 132 // /* 133 int num; 134 num = 0; 135 while(maxp != -1) 136 { 137 is_on[maxp] = 1; 138 139 trans[++num] = maxp;//没有初始化 140 rtrans[maxp] = num; 141 maxp = set[maxp]; 142 } 143 144 for(i = 1;i <= n;i++) 145 {// 146 147 if(!is_on[i]) 148 { 149 u = i; 150 while(!is_on[u]) 151 { 152 u = set[u]; 153 } 154 if(rdp[u] < dep[i] - dep[u]) 155 { 156 rdp[u] = dep[i]-dep[u]; 157 } 158 } 159 } 160 161 for(i = 1;i <= num;i++) 162 { 163 if(i == 1) 164 rp[i] = rdp[trans[i]]; 165 else 166 rp[i] = max(rp[i-1],i-1+rdp[trans[i]]); 167 } 168 for(i = num;i >= 1;i--) 169 { 170 if(i == num) 171 lp[i] = rdp[trans[i]]; 172 else 173 lp[i] = max(lp[i+1],num-i+rdp[trans[i]]); 174 } 175 int ans,ansb; 176 ans = 100000000; 177 ansb = -1; 178 for(i = 0;i < cnt;i+=2) 179 { 180 u = edges[i].u; 181 v = edges[i].v; 182 w = edges[i].w; 183 int subans; 184 if(is_on[u] && is_on[v]) 185 { 186 if(rtrans[u] > rtrans[v]) 187 { 188 int tmp; 189 tmp = u,u = v,v =tmp; 190 } 191 192 subans = max(rp[rtrans[u]],lp[rtrans[v]]); 193 if(ans > w*subans) 194 ans = w*subans,ansb = i/2+1; 195 196 } 197 else 198 { 199 if(ans > w*(num-1)) 200 ans = w*(num-1),ansb = i/2+1; 201 } 202 } 203 204 //*/ 205 206 // 207 printf("%d ",ansb); 208 209 } 210 return 0; 211 }