http://www.lydsy.com/JudgeOnline/problem.php?id=3246
中文题面
天地之初，世界尚在遥远的梦想之中。 Serpent(水蛇)生活的地方有N个水坑，编号为0，...，N - 1，有M条双向小路连接这些水坑。每两个水坑之间至多有一条路径（路径包含一条或多条小路）相互连接，有些水坑之间根本无法互通(即 M ≤ N-1 )。Serpent走过每条小路需要一个固定的天数，不同的小路需要的天数可能不同。 Serpent的朋友袋鼠希望新修 N - M - 1 条小路，让Serpent可以在任何两个水坑间游走。袋鼠可以在任意两个水坑之间修路，Serpent通过每条新路的时间都是L天。袋鼠希望找到一种修路方式使得修路之后Serpent在每两个水坑之间游走的最长时间最短。
Solution
然后自己大概讲一下
记录:dfs1→f[x][0]子树最远点,f[x][1]子树次远点
dfs2→f[x][0]所有点到其最大距离(直径)包括了父亲过来的f[x][1]所有点的次大距离
son[x]记录最远距离的那个儿子
转移:to[i]!=son[x],用次远点+w else 就用最远点更新(具体可参考代码)
构造:每一个联通块只有一个接点(树上的最远点到其距离最短),然后选哪个最大的接点,做中间点,其它接点都连向它,构成菊花树。。。
答案计算:max{树的直径,中间点+第二大点+l,第二大点+第三大点+2*l}
Code
// <dreaming.cpp> - Tue Sep 20 08:15:49 2016
// This file is made by YJinpeng，created by XuYike's black technology automatically.
// Copyright (C) 2016 ChangJun High School, Inc.
// I don't know what this program is. #include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define IN inline
#define RG register
#define MOD 1000000007
#define INF 1e9
using namespace std;
typedef long long LL;
const int MAXN=500010;
const int MAXM=1000010;
inline int max(int &x,int &y) {return x>y?x:y;}
inline int min(int &x,int &y) {return x<y?x:y;}
inline int gi() {
register int w=0,q=0;register char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')q=1,ch=getchar();
while(ch>='0'&&ch<='9')w=w*10+ch-'0',ch=getchar();
return q?-w:w;
}
bool vis[MAXN];
int f[MAXN][2],t,ans,k;
int to[MAXM],ne[MAXM],W[MAXM];
int fr[MAXN],son[MAXN],a[MAXN];
IN void add(RG int u,RG int v,RG int w){
to[++t]=v;ne[t]=fr[u];fr[u]=t;W[t]=w;
}
IN void dfs1(RG int x,RG int fa){
vis[x]=1;
for(RG int i=fr[x];i;i=ne[i])
if(!vis[to[i]]){
dfs1(to[i],x);
if(f[to[i]][0]+W[i]>f[x][0]){
son[x]=to[i];f[x][0]=f[to[i]][0]+W[i];
}
}
for(RG int i=fr[x];i;i=ne[i])
if(to[i]!=fa&&to[i]!=son[x])
f[x][1]=max(f[x][1],f[to[i]][0]+W[i]);
}
IN void dfs2(RG int x,RG int d,RG int fa){
if(d>f[x][0]){
f[x][1]=f[x][0];son[x]=fa;f[x][0]=d;
}else if(d>f[x][1])f[x][1]=d;
k=min(k,f[x][0]);ans=max(f[x][0],ans);
for(int i=fr[x];i;i=ne[i])
if(to[i]!=fa){
if(to[i]!=son[x])dfs2(to[i],f[x][0]+W[i],x);
else dfs2(to[i],f[x][1]+W[i],x);
}
}
int main()
{
freopen("dreaming.in","r",stdin);
freopen("dreaming.out","w",stdout);
RG int n=gi(),m=gi(),l=gi();
while(m--){
RG int u=gi()+1,v=gi()+1,w=gi();
add(u,v,w);add(v,u,w);
}t=0;
for(int i=1;i<=n;i++)
if(!vis[i]){
k=INF;dfs1(i,0);
dfs2(i,0,0);a[++t]=k;
}
sort(a+1,a+1+t);
if(t>=2)ans=max(ans,a[t]+a[t-1]+l);
if(t>=3)ans=max(ans,a[t-1]+a[t-2]+2*l);
printf("%d",ans);
return 0;
}