题解好像都是dfs 我来更一个两遍bfs吧，貌似更好写，别忘了开long long哦。

BFS

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

using namespace std;

typedef long long LL;
const int N = 1E5 + 10, M = 2 * N;

int n;
int h[M], e[M], ne[M], w[M], idx;
int dist[N];
bool st[N];

void add(int a, int b, int c) {
     e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void bfs(int x) {
    queue<int> q;
    q.push(x);
    dist[x] = 0;
    st[x] = true;

    while (q.size()) {
        int t = q.front();
        q.pop();

        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            if (st[j]) continue;
            dist[j] = dist[t] + w[i];
            q.push(j);
            st[j] = true;
        }
    }
}

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

    bfs(1);
    int maxdist = 0, maxidx = 0;
    for (int i = 1; i <= n; i++) {
        if (dist[i] > maxdist) {
            maxdist = dist[i];
            maxidx = i;
        }
    }

    memset(dist, 0, sizeof dist);
    memset(st, false, sizeof st);

    bfs(maxidx);
    maxdist = 0;
    for (int i = 1; i <= n; i++) {
        if (dist[i] > maxdist) maxdist = dist[i];
    }

    printf("%lld\n", (LL) 10 * maxdist + (LL) maxdist * (maxdist + 1) / 2);

    return 0;
}

DFS 用父节点

很巧妙

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

using namespace std;

typedef long long LL;
const int N = 1E5 + 10, M = 2 * N;

int n;
int h[M], e[M], ne[M], w[M], idx;
int dist[N];
bool st[N];

void add(int a, int b, int c) {
     e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int u, int father, int distance) {
    dist[u] = distance;

    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (j != father) dfs(j, u, distance + w[i]);
    }
}

int main() {
    scanf("%d", &n);
    memset(h, -1, sizeof h);
    for (int i = 0; i < n; 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 maxidx = 0, maxdist = 0;
    for (int i = 1; i <= n; i++) {
        if (dist[i] > maxdist) {
            maxdist = dist[i];
            maxidx = i;
        }
    }

    memset(dist, 0, sizeof dist);
    dfs(maxidx, -1, 0);
    maxdist = 0;
    for (int i = 1; i <= n; i++) {
        maxdist = max(dist[i], maxdist);
    }

    printf("%lld\n", (LL) maxdist * 10 + (LL) maxdist * (maxdist + 1) / 2);

    return 0;
}

DFS用状态数组

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

using namespace std;

typedef long long LL;
const int N = 1E5 + 10, M = 2 * N;

int n;
int h[M], e[M], ne[M], w[M], idx;
int dist[N];
bool st[N];

void add(int a, int b, int c) {
     e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int u, int distance) {
    dist[u] = distance;
    st[u] = true;

    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (st[j]) continue;
        dfs(j, distance + w[i]);
    }
}

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

    dfs(1, 0);
    int maxidx = 0, maxdist = 0;
    for (int i = 1; i <= n; i++) {
        if (dist[i] > maxdist) {
            maxdist = dist[i];
            maxidx = i;
        }
    }

    memset(dist, 0, sizeof dist);
    memset(st, false, sizeof st);
    dfs(maxidx, 0);
    maxdist = 0;
    for (int i = 1; i <= n; i++) {
        maxdist = max(dist[i], maxdist);
    }

    printf("%lld\n", (LL) maxdist * 10 + (LL) maxdist * (maxdist + 1) / 2);

    return 0;
}