C++

$\color{gold}{— > 蓝桥杯辅导课题解}$

思路：

DFS

$通过DFS找到树的直径即可$

$\color{red}{图解：}$

$时间复杂度：O(n)$

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

using namespace std;

const int N = 1e5 + 10;

int n;
struct Edge { // 每条边长就是一个结构体
    int id, w; // 编号，长度
};
vector<Edge> h[N];
int dist[N];

void dfs(int u, int father, int distance) { 
    /* 
    u:当前节点 
    father：当前节点的父节点（指：当前节点从哪个点来的，防止在遍历回去）
    distance：当前节点所能到达的最远距离
    */

    dist[u] = distance;

    for (auto node : h[u]) 
        if (node.id != father)  // 只有不往回走才遍历它
            dfs(node.id, u, distance + node.w);
}

int main() {
    cin >> n;
    for (int i = 0; i < n - 1; i ++) {
        int a, b, c;
        cin >> a >> b >> c; // 无向边
        h[a].push_back({b, c}); // 在a里面加入b,c
        h[b].push_back({a, c}); // 在b里面加入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];
    cout << s * 10 + s * (s + 1ll) / 2;

    return 0;
}