蓝桥杯省赛真题——大臣的旅费

输入样例：

5
1 2 2
1 3 1
2 4 5
2 5 4

输出样例：

135

分析：

本题实际上要求我们去求在图中最远两点之间的距离，也就是树的直径

我们先从某一个点出发，到达离其最远的点，然后再重复操作一次即可

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;const int N = 200010;
int n;
int e[N],ne[N],w[N],h[N],idx;
// 记录最远的点，记录最远的距离
int maxLen,maxd;// 领接表存储图
void add(int a,int b,int c)
{e[idx] = b,ne[idx] = h[a],w[idx] =c,h[a] = idx++;
}void dfs(int u,int fa,int d)
{for(int i=h[u];i!=-1;i=ne[i]){int j = e[i];int k = w[i];if(j==fa) continue;if(d+k>maxLen){maxLen = d+k;maxd = j;}dfs(j,u,d+k);}return;
}int main(void)
{cin >> n;memset(h,-1,sizeof h);for(int i=1;i<n;i++){int a,b,c;cin>>a >> b >> c;add(a, b, c);add(b,a,c);}// 第一次深搜dfs(1,-1,0);// 第二次深搜dfs(maxd,-1,0);cout << maxLen*10+(maxLen+1ll)*maxLen/2<< endl;return 0;
}