分析

理论：从树上任意点u开始DFS(BFS)遍历图，得到距离u最远的结点v,然后从v点开始DFS遍历图，得到距离v最远的结点w， 则v、w之间的距离就是树的直径。

证明 参考这里

得到直径d，ans=d×10+1+2+3+....+d= d×10+（d+1）× d ÷ 2。

求和结果加LL，基本常识。

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

#define ffor(i,s,e) for(int i=s;i<e;i++)
#define nl cout<<endl
#define out(x) cout<<x<<" "
typedef long long LL;
const int N=100010;

typedef struct node{
    int end,val;
}Node;

vector<Node> G[N];
int vis[N];

int start,maxD;//记录最远的端点，和当前的费用

void add(int s,int e,int v){
    G[s].push_back({e,v});
    G[e].push_back({s,v});
}

void init(){
    int n,s,e,v;
    cin>>n;
    ffor(i,0,n-1){
        scanf("%d%d%d",&s,&e,&v);
        add(s,e,v);
    }

    /*
    ffor(i,1,n+1){
        out(i);out('-');
        for(auto x: G[i]){
            out(x.end);
        }
        nl;
    }
    */

}

void dfs(int s,int weight){
    bool go=false;

    vis[s]=1;

    int n=G[s].size();
    ffor(i,0,n){
        int nxt=G[s][i].end;
        int v=G[s][i].val;
        if(!vis[nxt]){
            dfs(nxt,weight+v);
            go=true;
        }
    }

    if(!go){
        if(weight>maxD){
            maxD=weight;
            start=s;
        }
        return;
    }
}


// 直径存在maxD里
void getD(){
    dfs(1,0);//找到起点
    memset(vis,0,sizeof vis);
    dfs(start,0);//找到最长路

}
void getAns(){
    LL tmp=maxD*10;
    LL nxt=maxD+1;
    if(maxD&1) nxt>>=1;
    else maxD>>=1;

    out(tmp+maxD*nxt);nl;
}
void AcWing(){
    init();
    getD();
    getAns();
}

int main(){
//  init();
//  dfs(1,0);
//  out(start);out(maxD);nl;
//  memset(vis,0,sizeof vis);
//  dfs(start,0);
//  out(start); out(maxD);

    AcWing();
    return 0;
}