树的直径

CF1944E - Tree Compass

题意：给定一棵树，最初所有结点为白色。你可以进行操作：选定一个节点v和距离k，使树上与v的简单路径距离为k的所有点染色为黑色。构造操作序列，使操作次数最小化。

不难发现，影响操作次数的是树中最长的一条路径，即树的直径。所以我们只要找出树的直径并选定最中间的点（奇数长度则一个，偶数则两个），然后再使距离包含整条直径即可。

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

const int N = 2010;

int n, fa[N];
vector<int> e[N];

void add(int x, int y) {
    e[x].emplace_back(y);
    e[y].emplace_back(x);
}
// 两次bfs找树的直径
int find(int x) {
    queue<int> q;
    vector<int> dep(n + 10, -1);
    dep[x] = 0;
    fa[x] = -1;
    q.push(x);
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        for (auto nxt: e[now]) {
            if (dep[nxt] != -1) continue;
            fa[nxt] = now;
            dep[nxt] = dep[now] + 1;
            q.push(nxt);
        }
    }
    int ans = -1, ansid = 0;
    for (int i = 1; i <= n; i++) {
        if (dep[i] > ans) {
            ansid = i;
            ans = dep[i];
        }
    }
    return ansid;
}

void work() {
    cin >> n;
    for (int i = 1; i <= n; ++i)
        e[i].clear();
    for (int i = 1, x, y; i < n; ++i) {
        cin >> x >> y;
        add(x, y);
    }
    int x = find(1); // begin
    int y = find(x); // end
    vector<int> a;
    for (int i = y; i != -1; i = fa[i]) {
        a.emplace_back(i);
    } // fa[x] = -1
    int len = a.size();
    vector<pair<int, int>> ans;
    if (len & 1) {
        int p = a[len >> 1];
        for (int i = 0; i <= (len >> 1); ++i) {
            ans.emplace_back(p, i);
        }
    } else {
        int p1 = a[(len >> 1) - 1], p2 = a[len >> 1];
        for (int i = 1; i <= (len >> 1); i += 2){
            ans.emplace_back(p1, i);
            ans.emplace_back(p2, i);
        }
    }
    cout << ans.size() << '\n';
    for (auto [x, y]: ans) {
        cout << x << ' ' << y << '\n';
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--)
        work();
    return 0;
}