算法的核心思想

1. 求图中任意一点的距离最大的点
2. 再求该点在图中的距离最大的点，这个距离就是树的直径
   证明：分类讨论，反证法

1207-大臣的旅费

上述算法思想，本质上就是求图的最短路径，在所有的最短路径中选一个最大的值，因为每条路径都是唯一的，所以不存在最大路径和最短路径的说法，用bfs和dfs都能做，用单源最短路径也可以

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 100010;
int n;
struct node {
    int e, v;
};
vector<node> h[N];
int dist[N];

void dfs(int u, int father, int dis) {
    dist[u] = dis;
    for (auto node : h[u]) {
        if (node.e != father) dfs(node.e, u, dis + node.v);
    }
}


int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        int s, e, v;
        scanf("%d%d%d", &s, &e, &v);
        h[s].push_back({e, v});
        h[e].push_back({s, v});
    }
    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;
    }
    cout << dist[u] * 10 + dist[u] * (dist[u] + 1ll) / 2 << endl;
    return 0;
}

bfs

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <cstring>
using namespace std;
const int N = 100010;
int n;
struct edge {
    int e, v, next;
} ed[N * 2];
int cnt, h[N];

int dist[N], mark[N];

struct node {
    int now, dis;
};

void add(int s, int e, int v) {
    ed[cnt].e = e;
    ed[cnt].v = v;
    ed[cnt].next = h[s];
    h[s] = cnt++;
}


void bfs(int x) {
    queue<node> q;
    memset(mark, 0, sizeof(mark));
    dist[x] = 0, mark[x] = 1;
    q.push({x, 0});
    //cout << "befor while" << endl;
    while (!q.empty()) {
        auto t = q.front();
        //cout << "debug" << endl;
        //printf("now = %d, dis = %d\n", t.now, t.dis);
        q.pop();
        for (int i = h[t.now]; i != -1; i = ed[i].next) {
            if (ed[i].e == t.now || mark[ed[i].e] == 1) continue;
            dist[ed[i].e] = ed[i].v + t.dis;
            q.push({ed[i].e, ed[i].v + t.dis});
            mark[ed[i].e] = 1;
        }
        //cout << "------------" << endl;
    }
}

int main() {
    //cout << "2" << endl;
    cin >> n;
    memset(h, -1, sizeof(h));
    for (int i = 1; i < n; i++) {
        int s, e, v;
        scanf("%d%d%d", &s, &e, &v);
        add(s, e, v);
        add(e, s, v);
    }
    bfs(1);
    int u = 1;
    for (int i = 1; i <= n; i++) {
        if (dist[i] > dist[u]) u = i;
    }
    bfs(u);
    for (int i = 1; i <= n; i++) {
        if (dist[i] > dist[u]) u = i;
    }
    cout << dist[u] * 10 + dist[u] * (dist[u] + 1ll) / 2 << endl;
    return 0;
}