最直接的想法：对每个结点做一次 BFS，算出它到所有其他结点的距离，数一下偶数距离的有多少个。时间复杂度 O(n²)。
树是一种特殊的图——它一定是二分图。什么意思呢？我们可以把树上的所有结点染成两种颜色，使得每条边连接的两个结点颜色不同。
这是本题最核心的推理：
让我们用样例 2 的树来演示染色过程。从结点 1 开始 BFS，交替染成紫色和绿色。
// BFS 染色 int color[N]; int cnt[2]; // cnt[0]=偶数层, cnt[1]=奇数层 queue<int> q; // 从结点1开始 q.push(1); color[1] = 0; // 0=紫色(偶数层) cnt[0]++; while (!q.empty()) { int u = q.front(); q.pop(); for (int v : adj[u]) { if (color[v] == -1) { color[v] = color[u] ^ 1; cnt[color[v]]++; q.push(v); } } } // 输出答案 for (int i = 1; i <= n; i++) cout << cnt[color[i]] << ' ';
选一个起点，看看树上每个结点到它的距离是奇还是偶。你会发现：同色 = 偶数距离，异色 = 奇数距离。
/* * P11962 [GESP202503 六级] 树上漫步 * 核心思路：BFS二分图染色，同色=偶数步可达 * 时间复杂度 O(n) */ #include <bits/stdc++.h> using namespace std; const int N = 200005; vector<int> adj[N]; // 邻接表存树 int color[N]; // 染色：0=偶数层, 1=奇数层 int cnt[2]; // cnt[0]=偶数层个数, cnt[1]=奇数层个数 int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; // 读入 n-1 条边，建邻接表 for (int i = 0; i < n - 1; i++) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } // 初始化：所有结点未染色 memset(color, -1, sizeof(color)); // BFS 从结点 1 开始染色 queue<int> q; q.push(1); color[1] = 0; // 结点1是第0层(偶数) cnt[0]++; // 偶数层+1 while (!q.empty()) { int u = q.front(); q.pop(); for (int v : adj[u]) { if (color[v] == -1) { // 未染色 color[v] = color[u] ^ 1; // 异或1：0变1, 1变0 cnt[color[v]]++; // 对应颜色计数+1 q.push(v); } } } // 输出每个结点的答案 for (int i = 1; i <= n; i++) { cout << cnt[color[i]] << " "; // color[i]=0 → 输出偶数层个数 // color[i]=1 → 输出奇数层个数 } cout << endl; return 0; }
adj[u].push_back(v); adj[v].push_back(u);memset(color, -1, sizeof(color));color[v] = color[u] ^ 1; —— 这行是灵魂！^ 1 是异或运算：0 ^ 1 = 1（偶数层 → 奇数层）1 ^ 1 = 0（奇数层 → 偶数层）cnt[color[v]]++ 把对应颜色的计数器 +1。
cout << cnt[color[i]] << " ";| 结点 | 颜色 | 同色结点 | 答案 |
|---|---|---|---|
| 1 | 紫(偶) | 1, 2 | 2 |
| 2 | 紫(偶) | 1, 2 | 2 |
| 3 | 绿(奇) | 3 | 1 |
2 2 1 ✅ 与样例一致！| 结点 | 颜色 | 同色结点 | 答案 |
|---|---|---|---|
| 1 | 紫(偶) | 1, 2, 4 | 3 |
| 2 | 紫(偶) | 1, 2, 4 | 3 |
| 3 | 绿(奇) | 3 | 1 |
| 4 | 紫(偶) | 1, 2, 4 | 3 |
3 3 1 3 ✅ 与样例一致！来检验一下你的理解吧！共 6 道题。