算法1

思路:走一公里11,两公里12,三公里13,所以旅费为11,12,13,14.....,第x公里10+x,求和之后是10x+x*(x+1)/2,等差数列求和,这个题相当于一个无向图求最长距离,h[1]:[2,2],[3,1];h[2]:[1,2],[4,5],[5,4];h[3]:[1,1]....化成一棵树

C++ 代码

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

const int N=100010;

int n;

struct Edge{ //定义一个结构体,第一个点是编号,第二个是长度
    int id,w;
};

vector<Edge> h[N];
int dist[N];

void dfs(int u,int father,int distance){
    dist[u]=distance;
    for(auto node :h[u]){
        if(node.id!=father){//如果节点不往回走
            dfs(node.id,u,distance+node.w);

        }
    }
}


int main(){

    scanf("%d",&n);
    for(int i=0;i<n-1;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        h[a].push_back({b,c});
        h[b].push_back({a,c});

    }

    dfs(1,-1,0);

    int u=1;//从根结点开始遍历
    for(int i=1;i<=n;i++){

        if(dist[i]>dist[u])
            u=i;

    }

    dfs(u,-1,0);//循环两次
    for(int i=1;i<=n;i++){

        if(dist[i]>dist[u])
            u=i;

    }
    int s=dist[u];
    printf("%lld\n",s*10+s*(s+1ll)/2);//这里答案会爆int,所以写成lld
    return 0;
}