树的直径裸体,要两次dfs,第一次dfs求出距离1号点的最远的点设为u
第二次dfs以u为起点求距离最远的点,这时候求出来的距离就是树的直径。
时间复杂度:O(n)
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100010, M = 2 * N;
int h[N], e[M], ne[M], w[M], idx;
int dist[N];
int n;
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) {
for(int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if(j == fa) continue;
dist[j] = dist[u] + w[i];
dfs(j, u);
}
}
int main() {
cin >> n;
memset(h, -1, sizeof h);
for(int i = 0;i < n - 1; ++ i) {
int a, b, c;
cin >> a >> b >> c;
add(a, b, c), add(b, a, c);
}
dfs(1, -1);
int id = 1;
for(int i = 1;i <= n; ++ i) {
if(dist[id] < dist[i]) id = i;
}
memset(dist, 0, sizeof dist);
dfs(id, -1);
LL ans = 0;
for(int i = 1;i <= n; ++ i) {
ans = max(ans, (LL)dist[i]);
}
cout << ans * (ans + 1ll) / 2 + ans * 10 << endl;
return 0;
}