题目大意
给出一个缺若干条边的树，现在让你填一些长度为定值的边，，使得整个树的直径最小。
思路
给一个详细的网址，讲的非常明白。
还有数据范围是50w。
CODE;int points,edges,cost;int head[MAX],total;int _next[MAX << 1],aim[MAX << 1],length[MAX << 1];int father[MAX],dis[MAX];int f[MAX];int Find(int x){if(f[x] == x) return x;return f[x] = Find(f[x]);}inline void Add(int x,int y,int len){_next[++total] = head[x];aim[total] = y;length[total] = len;head[x] = total;}int max_length[MAX],next_length[MAX];int max_son[MAX];void DFS(int x,int last){father[x] = last;for(int i = head[x]; i; i = _next[i]) {if(aim[i] == last) continue;DFS(aim[i],x);if(max_length[aim[i]] + length[i] > max_length[x]) {max_length[x] = max_length[aim[i]] + length[i];max_son[x] = aim[i];}}for(int i = head[x]; i; i = _next[i]) {if(aim[i] != last && aim[i] != max_son[x])next_length[x] = max(next_length[x],max_length[aim[i]] + length[i]);}}int g[MAX];int cnt,now_tree;int __max[MAX],__min[MAX];void Calc(int x,int last){for(int i = head[x]; i; i = _next[i]) {if(aim[i] == last) continue;g[aim[i]] = max(g[x],max_son[x] == aim[i] ? next_length[x]:max_length[x]) + length[i];int now = max(g[aim[i]],max_length[aim[i]]);__max[now_tree] = max(__max[now_tree],now);__min[now_tree] = min(__min[now_tree],now);Calc(aim[i],x);}}int main(){cin >> points >> edges >> cost;for(int i = 1; i <= points; ++i)f[i] = i;for(int x,y,z,i = 1; i <= edges; ++i) {scanf(“%d%d%d”,&x,&y,&z);++x,++y;Add(x,y,z),Add(y,x,z);int fx = Find(x),fy = Find(y);if(fx != fy)f[fx] = fy;}int ans = 0;int max_1 = 0,max_2 = 0,max_3 = 0;for(int i = 1; i <= points; ++i)if(f[i] == i) {++cnt;now_tree = i;DFS(i,0);g[i] = 0;__max[i] = __min[i] = max_length[i];Calc(i,0);ans = max(ans,__max[i]);if(__min[i] > max_1) {max_3 = max_2;max_2 = max_1;max_1 = __min[i];}else if(__min[i] > max_2) {max_3 = max_2;max_2 = __min[i];}elsemax_3 = max(max_3,__min[i]);}if(cnt > 1) ans = max(ans,max_1 + max_2 + cost);if(cnt > 2) ans = max(ans,max_2 + max_3 + (cost << 1));cout << ans << endl;return 0;}
而它的种子，就是它生命的延续，继续承受风，
