BD 都太恶心，不写题解了。

2108E - Spruce Dispute

结论：以重心为根，删去深度最浅的叶子，再按 DFS 序染色。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        vector<vector<int>> E(n);
        for (int i = 1; i < n; i++) {
            int u, v;
            cin >> u >> v;
            u--, v--;
            E[u].push_back(v);
            E[v].push_back(u);
        }

		// 找重心 
        vector<int> siz(n), mss(n);
        auto dfs = [&](this auto&& dfs, int u, int p) -> void {
            siz[u] = 1;
            for (auto v : E[u]) {
                if (v == p) continue;
                dfs(v, u);
                siz[u] += siz[v];
                mss[u] = max(mss[u], siz[v]);
            }
        };
        dfs(0, -1);

        int s = 0; // 重心 
        for (int u = 0; u < n; u++) {
            mss[u] = max(mss[u], siz[0] - siz[u]);
            if (siz[u] && mss[u] <= siz[0] / 2) {
                s = u;
            }
        }
        // 以上找重心 

        vector<pair<int, int>> leaf;
        vector<int> dep(n);
        vector<int> order;
        auto dfs2 = [&](this auto&& dfs2, int u, int p) -> void {
            order.push_back(u);
            for (auto v : E[u]) {
                if (v == p) continue;   
                dep[v] = dep[u] + 1;
                dfs2(v, u);
            }
            if (E[u].size() == 1) leaf.push_back({dep[u], u});
        };
        dfs2(s, -1);

        int t = (*min_element(leaf.begin(), leaf.end())).second;
        
        cout << t + 1 << " " << E[t][0] + 1 << endl;

        vector<int> ans(n, -1);
        int now = 0;
        for (auto u : order) {
            if (u != max(t, E[t][0])) {
                ans[u] = (now++) % (n / 2);
            }
        }
        
        for (int i = 0; i < n; i++) {
            cout << (++ans[i]) << " ";
        }
        cout << endl;
    }
   
    return 0;
}