acwing1207. 大臣的旅费

题目

很久以前，T王国空前繁荣。

为了更好地管理国家，王国修建了大量的快速路，用于连接首都和王国内的各大城市。

为节省经费，T国的大臣们经过思考，制定了一套优秀的修建方案，使得任何一个大城市都能从首都直接或者通过其他大城市间接到达。

同时，如果不重复经过大城市，从首都到达每个大城市的方案都是唯一的。

J是T国重要大臣，他巡查于各大城市之间，体察民情。

所以，从一个城市马不停蹄地到另一个城市成了J最常做的事情。

他有一个钱袋，用于存放往来城市间的路费。

聪明的J发现，如果不在某个城市停下来修整，在连续行进过程中，他所花的路费与他已走过的距离有关，在走第x千米到第x+1千米这一千米中（x是整数），他花费的路费是x+10这么多。也就是说走1千米花费11，走2千米要花费23。

J大臣想知道：他从某一个城市出发，中间不休息，到达另一个城市，所有可能花费的路费中最多是多少呢？

题解

在无环图中，从任意一点u开始，找到距离u最远的点x，再从x开始，找到距离x最远的点，那么这两点就是直径（两点最大距离）

#include<iostream>
#include<cstring>
using namespace std;
const int N=1e5+10;
int h[N],ne[N*2],w[N*2],e[N*2],idx;
int n,dist[N];

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 father,int distence){
    dist[u]=distence;
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j!=father){
            dfs(j,u,distence+w[i]);
        }
    }
    
}

int main(){
    cin>>n;
    memset(h,-1,sizeof h);
    for(int i=0;i<n-1;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
        add(b,a,c);
    }
    dfs(1, -1, 0);

    int u = 1;
    for (int i = 2; i <= n; i ++ )
        if (dist[u] < dist[i])
            u = i;

    dfs(u, -1, 0);

    for (int i = 1; i <= n; i ++ )
        if (dist[u] < dist[i])
            u = i;

    printf("%lld\n", dist[u] * 10 + (dist[u] + 1ll) * dist[u] / 2);
    return 0;
}