树的直径

定义：树上任意两节点之间最长的简单路径即为树的「直径」
显然，一棵树可以有多条直径，他们的长度相等。
可以用两次 DFS 或者树形 DP 的方法在 O(n) 时间求出树的直径。

求树的直径的方法：

1. 任取一点作为起始点k，找到距离该点最远的一个点v。

2. 从点v开始搜，找到距离点v最远的一点u，则uv间的距离是树的直径。

//1KB=1024B（字节），1MB=1024KB，所以1MB大约等于100w字节（1e6）64MB = 6400w字节 （6*1e7）
//int 占四字节
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 1e5 + 10;
const int M = 2*N;

int n;
int h[N],e[M],ne[M],idx=1,w[M]; //
bool st[N];
LL s[10100];
LL maxu,maxd;

void add(int a,int b,int d){
    e[idx] = b; ne[idx] = h[a]; h[a] = idx; w[idx] = d; idx++; //idx要最后再++
}

//求距离某个点u最远的点maxu,以及距离
void dfs(int u,int d){
    st[u] = true;
    for(int i = h[u];i!=-1;i=ne[i]){
        int j = e[i];
        if(!st[j]){
            st[j] = true;
            if(maxd < d+w[i]){
                //maxu是距离u最远的点，maxd是 u和maxu 的距离
                maxd = d+w[i];
                maxu = j;
            }
            dfs(j,d+w[i]);
            st[j] = false;
        }
    }
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    memset(h,-1,sizeof(h));
    //这里是到n-1
    for(int i=0;i<n-1;i++){
        int a,b,d;
        cin >> a >> b >> d;
        add(a,b,d); add(b,a,d);
    }
    // cout << s[4] << "\n";
    // int ans,max=0,pos;
    // for(int i=2;i<=n;i++){
    //     memset(st,0,sizeof(st));
    //     ans = dfs(1,i,0);
    //     if(ans > max){
    //         max = ans;
    //         pos = i;
    //     }
    // }
    dfs(1,0);
    memset(st,0,sizeof(st));
    dfs(maxu,0);
    // cout << u << pos;
    // memset(st,0,sizeof(st));
    // cout << maxd; 
    //n(a1+an)/2
    cout << ( 11 + (11+maxd-1) )*maxd/2;
    // cout << s[maxd];
    return 0;
}