0先翻译题目：到底让我们干什么？
题目很长，其实只说了三件事：
② 从某个点出发，每次沿边走一步，走任意多步都可以，路上允许重复走。
③ 要求最后停下来的步数是偶数（0 步也算，就是停在起点自己）。
问：对于每个起点，数一数有多少个点能作为「偶数步终点」。
（因为：想要偶数步停在 v ⟺ dist(u,v) 是偶数。为什么？马上见第 1 节！）
记住这个目标，我们慢慢拆：距离的奇偶性、深度、一次遍历数答案。
1三个关键发现（原理）
发现①：走一步，奇偶就翻转一次
每走一条边，走的步数就 +1，奇偶性翻转：偶→奇→偶→奇…… 所以任何一条从 u 到 v 的走法，它的步数奇偶 = dist(u,v) 的奇偶。（树里没有「绕一圈变回奇数步」的怪圈——树是二部图！）
发现②：偶数步结束 ⟺ 距离是偶数
走法想比最短距离多走几步？完全可以：走到一个邻居再走回来，正好多 2 步，终点不变。所以「偶数步能停在 v」=「dist(u,v) 是偶数」。
发现③：距离奇偶 ⟺ 深度奇偶相同
随便挑一个根（比如 1 号点），记 depth[x] 为 x 到根的距离。树上任意两点 u、v：
dist(u,v) 是偶数 ⟺ depth[u] 和 depth[v] 奇偶相同
因为 u→v 的路径长度 = depth[u] + depth[v] − 2×depth[LCA]，后面这项永远是偶数，不影响奇偶！
节点 i 的答案 = cntE（如果 depth[i] 是偶数）或 cntO（如果 depth[i] 是奇数）。
也就是说：整棵树只有两种答案！一次 BFS/DFS 算出深度、数出 cntE/cntO，每个点直接对号入座，复杂度 O(n)。
2动画①：漫步奇偶性（亲眼验证发现①和②）
这是一棵 7 个点的树。点一下任意节点把它设成起点，所有点立刻被染色：绿色 = 离起点距离为偶数（可以偶数步到达），灰色 = 距离为奇数（永远只能用奇数步到达）。然后点「走一步」，看漫步的步数奇偶和脚下节点的颜色对不对得上。
3动画②：算法执行全过程（DFS 染色 → 统计 → 填答案）
把 1 号点当根，用 DFS 给每个点标深度（蓝色 = 偶数深度，橙色 = 奇数深度），一边走一边数 cntE / cntO；DFS 结束后，按「对号入座」给每个点填上答案。这就是程序跑的全过程。
数一数：偶数深度的点 5 个（1、4、5、6、7），奇数深度的点 2 个（2、3）。所以 1、4、5、6、7 的答案都是 5，2、3 的答案都是 2——和动画①里点节点验证的结果完全一致！
4推导总结（一步步来）
两个样例对一对（公式算的和题目输出）
📖 样例 1：n=3，边 1-3、2-3 → 输出 "2 2 1"
以 1 为根：depth[1]=0（偶），depth[3]=1（奇），depth[2]=2（偶）。
cntE = 2（节点 1、2），cntO = 1（节点 3）。
node 1（偶）→ 2，node 2（偶）→ 2，node 3（奇）→ 1。输出 2 2 1 ✓
📖 样例 2：n=4，边 1-3、3-2、4-3 → 输出 "3 3 1 3"
以 1 为根：depth[1]=0（偶），depth[3]=1（奇），depth[2]=2（偶），depth[4]=2（偶）。
cntE = 3（节点 1、2、4），cntO = 1（节点 3）。
node 1→3，node 2→3，node 3→1，node 4→3。输出 3 3 1 3 ✓
5C++ 代码（BFS 版，稳妥不爆栈）
n 最大 2×10⁵，如果用递归 DFS，一条长链会让递归栈爆掉，所以这里用队列 BFS——和迷宫最短路一模一样的模板，只是把「步数」换成「深度」。
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
vector<int> g[N]; // 邻接表存树
int depth[N]; // depth[x]：x 到根的距离
bool vis[N];
int cnt[2]; // cnt[0] = 偶数深度个数，cnt[1] = 奇数深度个数
queue<int> q;
int main() {
int n;
cin >> n;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
// BFS 求深度（1 号点当根，深度 0）
q.push(1);
vis[1] = true;
while (!q.empty()) {
int u = q.front(); q.pop();
cnt[depth[u] % 2]++; // 自己进对应的桶
for (int i = 0; i < (int)g[u].size(); i++) {
int v = g[u][i];
if (vis[v]) continue; // 爸爸或已访问过
vis[v] = true;
depth[v] = depth[u] + 1; // 深度 = 爸爸深度 + 1
q.push(v);
}
}
// 对号入座：深度和自己同奇偶的节点总数
for (int i = 1; i <= n; i++) {
cout << cnt[depth[i] % 2];
if (i < n) cout << " ";
}
cout << endl;
return 0;
}时间复杂度 O(n)：每个点入队出队各一次。空间 O(n)：邻接表 + 深度数组。
📖 递归 DFS 版（代码更短，但长链大数可能爆栈，慎用）
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
vector<int> g[N];
int depth[N], cnt[2];
void dfs(int u, int fa) {
cnt[depth[u] % 2]++;
for (int v : g[u]) {
if (v == fa) continue; // 别走回爸爸
depth[v] = depth[u] + 1;
dfs(v, u);
}
}
int main() {
int n; cin >> n;
for (int i = 1; i < n; i++) {
int u, v; cin >> u >> v;
g[u].push_back(v); g[v].push_back(u);
}
dfs(1, 0);
for (int i = 1; i <= n; i++)
cout << cnt[depth[i] % 2] << (i == n ? "\n" : " ");
return 0;
}6小测验（点选项看对错）
1️⃣ 树上两点 dist(u,v) = 3（奇数）。从 u 出发，有可能偶数步结束在 v 吗？
2️⃣ 一条链 1-2-3-4-5（5 个点排成一行）。从节点 1 出发，偶数步能到达几个节点？
3️⃣ 星星图：1 个中心点连着 4 个叶子（共 5 个点）。中心节点的答案是多少？
4️⃣ 还是那颗星星图（中心+4 叶子）。一个叶子的答案是多少？
5️⃣ 判断题：每个节点的答案至少是 1（因为 0 步就结束在自己）。
6️⃣ n ≤ 2×10⁵ 时，应该怎么解？
7考点总结（这道题在考什么）
- 树的表示：邻接表
vector<int> g[N]，n−1 条边、无环——见到 n 个点 n−1 条边就该想到树。 - BFS/DFS 求深度：一层层或递归地算出每个点到根的距离，是树的入门基本功。
- 奇偶性思维：把「任意长走法」化成「最短距离 + 2k」，奇偶只看最短距离——这是最核心的一步。
- 深度奇偶 ⟺ 距离奇偶：树上两点的距离 = depth[u]+depth[v]−2×depth[LCA]，LCA 项是偶数，直接扔掉。
- 只统计两种答案：cntE / cntO 两个桶，所有点对号入座，O(n) 解决。