思路分析:

• 根据题目描述可以发现给出的是一棵树，并且求的是树的最大直径，直接用树形Dp模板解决:

• 状态表示: f[u][0] 表示以u为根节点的树从u出发最远能到达的最大距离，f[u][1]表示u出发到达的次远距离;我这里偷懒直接用d1,d2表示，不需要重新开辟数组f;

• 状态转移: 由上面的定义，在穿过过u点的直径为f[u][0]+f[u][1], 则最大直径就是每一个穿过u的直径的最大值;

• 设j为u的子节点，可以采用遍历f[j][0]+w[u][j]来更新f[u][0]和f[u][1];

• 得到最长直径后，由题意变形一下可以求出答案

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=1e5+10,M=2*N;
int h[N],e[M],w[M],ne[M],idx;
int n;
int res=0;
void init()
{
    memset(h,-1,sizeof(h));
    idx=0;
}
void add(int a,int b,int c)
{
    e[idx]=b;
    ne[idx]=h[a];
    w[idx]=c;
    h[a]=idx++;
}
int dfs(int u,int fa)
{
    int d1=0,d2=0;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(j==fa) continue;
        int d=dfs(j,u)+w[i];
        if(d>d1) {
            d2=d1;
            d1=d;
        }
        else if(d>d2) d2=d;
    }
    res=max(res,d1+d2);
    return d1;
}
int main()
{
    scanf("%d",&n);
    init();
    int a,b,c;
    for(int i=0;i<n-1;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
        add(b,a,c);
    }
    int p=dfs(1,-1);
    ll ans=(ll)res*(res+1)/2+(ll)res*10;
    cout<<ans<<endl;
    return 0;
}