算法:树的直径
定义:树中距离最远的两个点之间的距离被称为树的直径。
(1)任取一点作为起点x,找到距离该点最远的一个点y;
(2)再找到距离y最远的一点z,那么y、z之间的路径就是一条直径。
const int N = 1e6 + 10;
int e[N], h[N], w[N], ne[N], idx;
int n, maxd, maxu;
void add(int a, int b, int c)
{
w[idx] = c, e[idx] = b;
ne[idx] = h[a], h[a] = idx ++;
}
void dfs(int u, int fa, int d)
{
for(int i = h[u]; ~ i; i = ne[i])
{
int j = e[i];
int k = w[i];
if(j == fa) continue;
if(maxd < d + k)
{
maxd = d + k;
maxu = j;
}
dfs(j, u, d + k);
}
}
int main()
{
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(maxu, -1, 0);
cout << (maxd * 10 + (ll)(maxd + 1) * maxd / 2) << endl;
return 0;
}