给定一棵 \(n\) 个点的树，可以执行任意次以下操作：选定一个距离 \(u\) ，并将与 \(u\) 距离为 \(d\) 的点都染色。求使得所有节点都染上颜色的最小操作次数，并输出方案。
\(n \leq 2000\)
看着数据范围，朝着 \(O(n^2)\) 的 dp 去想，但是没有想出来。然后又尝试大胆猜测， \(d\) 只有可能等于 \(1\) ，但是这个结论很不靠谱。尝试过从链的角度切入，但感觉没有什么东西可以挖掘，然后就弃了。
然后赛后发现看错题了，以为每个节点只能操作一次。
绷不住了
实际上链的情形很好想。关键是怎么挪到一般的树上。这个桥梁就是树的直径。找到树的直径，然后从直径中点一圈一圈往外染色，这样必然能够染完。
如何证明是最优方案？
因为一次操作最多将直径上的两个点染色，上面给出的方案也一样。所以不管怎么操作，都不会更优。
关键是怎么想到是直径呢……这就很玄学
所以为什么 \(n\) 要给 \(2000\) ……
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 2005;
struct Edg {
int lst, ed;
}e[N << 1];
int n = 0, ne = 0;
int nte[N], dis[N], fa[N], sta[N];
void NewEdg(int u, int v) {
ne++;
e[ne].lst = nte[u];
e[ne].ed = v;
nte[u] = ne;
}
void dfs(int x) {
for (int i = nte[x]; i; i = e[i].lst) {
if (e[i].ed == fa[x]) continue;
dis[e[i].ed] = dis[x] + 1;
fa[e[i].ed] = x;
dfs(e[i].ed);
}
}
int GetFar(int x) {
dis[x] = 1; fa[x] = 0;
dfs(x);
int p = 1;
for (int i = 2; i <= n; i++)
if (dis[i] > dis[p]) p = i;
return p;
}
int main() {
int T = 0;
scanf("%d", &T);
for (int G = 1; G <= T; G++) {
scanf("%d", &n);
ne = 0;
for (int i = 1; i <= n; i++)
nte[i] = 0;
for (int i = 1; i <= n - 1; i++) {
int u = 0, v = 0;
scanf("%d%d", &u, &v);
NewEdg(u, v);
NewEdg(v, u);
}
int x = GetFar(1);
int y = GetFar(x);
int p = y, top = 0;
while(p) {
sta[++top] = p;
p = fa[p];
}
if (dis[y] & 1) {
printf("%d\n", dis[y] / 2 + 1);
p = sta[top / 2 + 1];
for (int i = 0; i <= dis[y] / 2; i++)
printf("%d %d\n", p, i);
} else {
printf("%d\n", dis[y] / 2 + (dis[y] % 4 == 2));
p = sta[top / 2];
for (int i = 1; ; i += 2) {
if (top / 2 - i <= 0 && top / 2 + i > top)
break;
printf("%d %d\n", p, i);
}
p = sta[top / 2 + 1];
for (int i = 1; ; i += 2) {
if (top / 2 - i <= 0 && top / 2 + i > top)
break;
printf("%d %d\n", p, i);
}
}
}
return 0;
}