P4408 [NOI2003]逃学的小孩（树的直径）

题目描述

Chris家的电话铃响起了，里面传出了Chris的老师焦急的声音：“喂，是Chris的家长吗？你们的孩子又没来上课，不想参加考试了吗？”一听说要考试，Chris的父母就心急如焚，他们决定在尽量短的时间内找到Chris。他们告诉Chris的老师：“根据以往的经验，Chris现在必然躲在朋友Shermie或Yashiro家里偷玩《拳皇》游戏。现在，我们就从家出发去找Chris，一但找到，我们立刻给您打电话。”说完砰的一声把电话挂了。

Chris居住的城市由N个居住点和若干条连接居住点的双向街道组成，经过街道x需花费Tx分钟。可以保证，任两个居住点间有且仅有一条通路。Chris家在点C，Shermie和Yashiro分别住在点A和点B。Chris的老师和Chris的父母都有城市地图，但Chris的父母知道点A、B、C的具体位置而Chris的老师不知。

为了尽快找到Chris，Chris的父母会遵守以下两条规则：

如果A距离C比B距离C近，那么Chris的父母先去Shermie家寻找Chris，如果找不到，Chris的父母再去Yashiro家；反之亦然。
Chris的父母总沿着两点间唯一的通路行走。

显然，Chris的老师知道Chris的父母在寻找Chris的过程中会遵守以上两条规则，但由于他并不知道A，B，C的具体位置，所以现在他希望你告诉他，最坏情况下Chris的父母要耗费多长时间才能找到Chris？

输入格式

输入文件第一行是两个整数N（3 ≤ N ≤ 200000）和M，分别表示居住点总数和街道总数。

以下M行，每行给出一条街道的信息。第i+1行包含整数Ui、Vi、Ti（1≤Ui, Vi ≤ N，1 ≤ Ti ≤ 1000000000），表示街道i连接居住点Ui和Vi，并且经过街道i需花费Ti分钟。街道信息不会重复给出。

输出格式

输出文件仅包含整数T，即最坏情况下Chris的父母需要花费T分钟才能找到Chris。

输入输出样例

输入

4 3

1 2 1

2 3 1

3 4 1

输出
4

思路分析：
　　这道题要求我们求的是Chris的父母先后到两个朋友家的时间之和的最大值，我们令起点为A点，两个朋友家分别为B和C，那么很明显我们要的答案为
dis（B,C）+ min（dis（A,B），dis（A,C）），由于题目中说道任两个节点之间都有且只有一条道路，那么我们最终建的图就会是一个树的形状。我们当B,C

间距离最大时即当B,C为树的直径时可以取得最优，所以我们跑4遍DFS即可，第一遍任取一点求距离它最远的点，设为cnt1，第二遍从cnt1开始，求到cnt1距离最大的点

则此时cnt1-cnt2为树的直径。第三次，第四次分别从cnt1和cnt2出发，求出每个点到cnt1和cnt2的距离，最后从1到n扫一遍求出最优即可。

关于为什么B，C为直径时最优的贪心证明大家可以看一下这里

网址：https://www.luogu.com.cn/blog/ILikeDuck/solution-p4408

附上代码：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int N=1e6+10;
 6 long long dis1[N],dis2[N];
 7 int n,m,cnt1,cnt2;
 8 struct Node{
 9     int next,to;
10     long long dis;
11 }edge[N];
12 int Head[N],tot;
13 void Add(int x,int y,long long z){
14     edge[++tot].to=y;
15     edge[tot].dis=z;
16     edge[tot].next=Head[x];
17     Head[x]=tot;
18 }
19 void dfs1(int u,int fa){  //四次DFS 
20     for(int i=Head[u];i;i=edge[i].next){
21         int v=edge[i].to;
22         if(v==fa) continue;
23         dis1[v]=dis1[u]+edge[i].dis;
24         if(dis1[v]>dis1[cnt1]) cnt1=v;
25         dfs1(v,u);
26     }
27 }
28 void dfs2(int u,int fa){
29     for(int i=Head[u];i;i=edge[i].next){
30         int v=edge[i].to;
31         if(v==fa) continue;
32         dis2[v]=dis2[u]+edge[i].dis;
33         if(dis2[v]>dis2[cnt2]) cnt2=v;
34         dfs2(v,u);
35     }
36 }
37 void dfs3(int u,int fa){
38     for(int i=Head[u];i;i=edge[i].next){
39         int v=edge[i].to;
40         if(v==fa) continue;
41         dis1[v]=dis1[u]+edge[i].dis;
42         dfs3(v,u);
43     }
44 }
45 void dfs4(int u,int fa){
46     for(int i=Head[u];i;i=edge[i].next){
47         int v=edge[i].to;
48         if(v==fa) continue;
49         dis2[v]=dis2[u]+edge[i].dis;
50         dfs4(v,u);
51     }
52 }
53 int main(){
54     scanf("%d%d",&n,&m);
55     for(int i=1;i<=m;++i){
56         int x,y,z;
57         scanf("%d%d%d",&x,&y,&z);
58         Add(x,y,z);Add(y,x,z);
59     }
60     dfs1(1,0);
61     dfs2(cnt1,0);
62     long long ans=dis2[cnt2];
63     memset(dis1,0,sizeof(dis1));
64     memset(dis2,0,sizeof(dis2));
65     dfs3(cnt1,0);dfs4(cnt2,0);
66     long long temp=0;
67     for(int i=1;i<=n;++i){   //比较那一个点作为A点好. 
68         long long d=min(dis1[i],dis2[i]);
69         if(d>temp) temp=d;
70     }
71     printf("%lld
",temp+ans);
72     return 0;
73 }