方法一:

通过题设信息，每两个点之间均可达且每两个点之间路径唯一，故不存在环，n个点共n-1条边，说明路径形似一棵树。通过一遍DFS，找出距离根节点最长的路径和次长的路径，两路径根节点的距离(即两路径和)即为树的直径

代码:

#include<bits/stdc++.h>
using namespace std;

int N;
const int n = 100010;
// 路线数据类型 记录与当前点相连的路线的另一个点 以及路线长度
struct road
{
    int other;  // 当前路线边对应的另一个点的编号
    int d;      // 当前路线边的长度
};
vector<vector<road>> city(n);   // 维护每个城市向外相连的边
int diameter = 0; // 记录树的直径

// DFS函数返回从节点id出发的最长路径(深度)
int DFS(int id, int parent) 
{
    int max1 = 0, max2 = 0; // 记录最长、次长路径长度
    for(auto &c : city[id]) 
    {
        int nxt = c.other;
        if(nxt == parent) continue;
        int d = DFS(nxt, id) + c.d; // 从当前节点id经由节点nxt能够到达的最长路径长度
        if(d > max1) 
        {
            max2 = max1;
            max1 = d;
        } 
        else if(d > max2) 
            max2 = d;
    }
    diameter = max(diameter, max1 + max2);
    return max1;    // 返回从节点id出发的最长路径
}

int main()
{
    cin >> N;
    for(int i = 1; i < N;i ++)
    {
        int c1,c2,D;
        cin >> c1 >> c2 >> D;
        city[c1].push_back({c2,D});
        city[c2].push_back({c1,D});
    }

    DFS(1,-1);

    long long int cost = 0; // 记录总花费
    // 行驶第x km花费1x元 拆成 10 和 x 前者常数累加 后者等差累加
    cost += (long long int)diameter * 10;
    cost += (long long int)diameter * (diameter + 1) >> 1;
    cout << cost;
    return 0;
}

方法二:

求树的直径分两步:(两遍DFS)

1.任取一点x，找到其他n-1个点到x的距离，记录在dist[]中

2.找到距离x最远的点y，用y重复一遍1操作，得到其他n-1个点到y的距离，其中的最大值就是树的直径

原理:

距离任意点x最远的点y一定是树的某条直径的端点，距离树的某条直径的端点最远的点一定是直径的另一端点，这个最远距离即树的直径

证明:

图的存储:

本题采用邻接表形式，每个节点开个变长数组，存储该点连接的边的信息(编号、权值)

代码:

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

using namespace std;

const int N = 100010;

int n;          // 节点数目
struct Edge     // 边的信息
{
    int id, w;  // 另一端点 边权值
};
vector<Edge> h[N];  // 维护每个节点的边信息
int dist[N];        // dist[i]记录第i个点距离所选点的距离

// 参数
//   u         - 当前遍历的节点编号
//   father    - 当前节点的父节点编号 防止走回头路
//   distance  - 当前节点u与起点之间的距离
void dfs(int u, int father, int distance)
{
    dist[u] = distance;

    for (auto node : h[u])      // 遍历与节点u相连的所有边
        if (node.id != father)  // 若相邻节点不是父节点（防止重复访问）
            dfs(node.id, u, distance + node.w); // 递归调用dfs 更新相邻节点的距离:当前距离加上边的权值
}

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:找到距离根节点最远的点x
    dfs(1, -1, 0);

    int u = 1;
    for (int i = 1; i <= n; i ++ )
        if (dist[i] > dist[u])
            u = i;
    // 第二遍DFS:找到距离x最远的距离
    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);

    return 0;
}