先翻译一下题面，这道题要我们用两个人去遍历树上的所有点，问我们最短距离。
读完之后其实和前两天那题旅游非常像，我们要遍历一颗树上所有点，只要把所有边走两边然后减掉一条根到叶子的最长链就行了
那么这道题有两个人一起走，所以就是减掉树的直径。
问题转化到这里其实就非常好做了，树的直径我们可以用两边dfs和dp来做，这里我用的是dp，使用两个数组记录子树的最大长和次大长，加起来取个最大就行。
下附代码：
1 #include<cstdio> 2 #include<iostream> 3 #define ll long long 4 using namespace std; 5 ll res=0,head[100005],to[200005],Next[200005],len[200005],tot=0,f1[100005],f2[100005]; 6 int n,s; 7 void add(int a,int b,int c){ 8 Next[tot]=head[a],to[tot]=b,len[tot]=c; 9 head[a]=tot++; 10 } 11 void dfs(int x,int pre){ 12 ll ret=0; 13 for (int i=head[x]; i!=-1; i=Next[i]){ 14 int v=to[i]; 15 if (v!=pre){ 16 dfs(v,x); 17 if (f1[v]+len[i]>f1[x]){ 18 f2[x]=f1[x]; 19 f1[x]=f1[v]+len[i]; 20 } 21 else f2[x]=max(f2[x],f1[v]+len[i]); 22 } 23 } 24 res=max(res,f1[x]+f2[x]); 25 } 26 int main(){ 27 scanf("%d%d",&n,&s); 28 for (int i=1; i<=n; i++) head[i]=-1; 29 int sum=0; 30 for (int i=1; i<n; i++){ 31 int a,b,c; 32 scanf("%d%d%d",&a,&b,&c); 33 add(a,b,c); 34 add(b,a,c); 35 sum+=c; 36 } 37 dfs(s,-1); 38 printf("%lld",sum*2-res); 39 return 0; 40 }
原文：https://www.cnblogs.com/i-caigou-TT/p/13865304.html
