两次搜索
1. 第一次找距离根节点的路径中,权值最大的一个点的位置
2. 从该点出发,找距离自己最远的一个点,即树的直径
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 1e5 * 3;
int h[N],e[N],w[N],ne[N],id;
int dic[N];
int n;
void add(int u,int v,int t) {
e[id] = v, w[id] = t, ne[id] = h[u], h[u] = id++;
}
void dfs(int u,int father,int val) {
dic[u] = val;
for(int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if(v == father) continue;
dfs(v,u,val + w[i]);
}
}
int main() {
cin >> n;
memset(h,-1,sizeof h);
for(int i = 0; i < n; i++) {
int u,v,t;
cin >> u >> v >> t;
add(u,v,t);
add(v,u,t);
}
int u = 0;
// 第一次dfs 统计所有节点到根节点的路径
dfs(1,-1,0);
for(int i = 1; i <= n; i++)
if(dic[u] < dic[i]) u = i;
memset(dic,0x00,sizeof dic);
// 第二次 dfs 统计所有节点到u的距离
dfs(u,-1,0);
for(int i = 1; i <= n; i++)
if(dic[u] < dic[i]) u = i;
LL res = dic[u];
res = res * 10 + (res * (res + 1)) / 2;
cout << res << endl;
return 0;
}