大臣的旅费

#include<iostream>
#include <vector>
using namespace std;
const int N = 1e5 + 10;
typedef long long ll;

struct nod{
    int id ,l;
};
vector<nod>q[N];
int dis[N];
void  dfs(int u, int f, int dt)
{
    dis[u] = dt;
    for(auto g:q[u])
    {
        if(g.id != f)//防止回溯到父节点
        {
           dfs(g.id, u, dt + g.l);
        }
    }
}
int main()
{
    int n;
    cin >>n;
    for(int i = 1; i <= n - 1; i ++){
        int a, b, c;
        cin >> a >> b >>c;
        q[a].push_back({b, c});
        q[b].push_back({a, c});
    }
    dfs(1, -1, 0);//算出每个点到1的距离
    int u = 1;
    for(int i = 1; i<= n ; i ++)//找到距离1最远的点
    {
        if(dis[i] > dis[u])
        u = i;
    }
    dfs(u, -1, 0);//在找距离1最远的点距离最远的点
    for(int i = 1; i <= n; i ++)
    {
        if(dis[i] > dis[u])u = i;
    }
    int s = dis[u];
    cout << 10 * s + s * (s + 1ll) / 2 << endl;
    return 0;
}