248.树上漫步

题目分析

本题给定一棵具有 ( n ) 个结点的树，要求对每个结点 ( i )，求出从 ( i ) 出发，走偶数步（0 步、2 步、4 步……）能够结束漫步的结点个数。漫步过程中允许重复经过结点。

首先观察：在树上行走，每一步都是沿着边移动到相邻结点。如果我们按照行走的步数奇偶性来对可达结点分类，可以把树的结点集合分成两个部分：一部分是从起点出发走偶数步可达的结点，另一部分是走奇数步可达的结点。由于树是连通且无环的，它具有天然的二分图性质：我们可以将树的结点进行二染色（比如黑和白），使得任意相邻的两个结点颜色不同。

如果我们将树二染色，那么不难发现：从一个结点出发，走偶数步到达的结点一定与起点颜色相同；走奇数步到达的结点一定与起点颜色相反。这是因为每移动一步，颜色就会翻转一次。因此，从 ( i ) 出发经过偶数步能够到达的结点，就是与 ( i ) 同色的所有结点。

反之，是否与 ( i ) 同色的结点都能通过偶数步到达？由于树是连通的，且可以在任意结点间来回移动，我们总可以构造一条从 ( i ) 到任意同色目标结点 ( j ) 的路径。这条路径的长度可能是偶数，也可能是奇数。如果路径长度为偶数，则直接可达；如果为奇数，我们可以在路径终点额外来回走一条边（例如走到一个邻接点再返回），这样总步数增加 2，仍保持偶数。因此，只要起点和目标同色，就一定存在一条偶数步路径。所以答案就是：对于结点 ( i )，所有与 ( i ) 同色的结点个数。

解题思路

1. 二染色（黑白染色）
   以任意结点（如结点 1）为根，对树进行一次深度优先搜索（或广度优先搜索），将相邻结点染成不同颜色。可用颜色编号 0 和 1 来表示。
   在染色过程中，同时统计两种颜色的结点个数，记为 cnt[0] 和 cnt[1]。

2. 计算答案
   对于结点 ( i )，若其颜色为 c，则答案为 cnt[c]，即与它同色的结点总数。

3. 输出
   按顺序输出每个结点的答案即可。

算法说明

参考代码中采用邻接表存储树，并使用 DFS 实现染色与计数。

• h[u]：结点 ( u ) 的第一条边的编号（链式前向星）。
• to[et] 和 nx[et]：存储边的目标结点和下一条边的编号。
• bel[u]：结点 ( u ) 的颜色（0 或 1）。
• cnt[0/1]：两种颜色的结点数量。

DFS 函数 dfs(u, c, f) 表示当前访问结点 ( u )，赋予颜色 ( c )，父结点为 ( f )。
将 bel[u] 设为 c，令 cnt[c]++，然后遍历 ( u ) 的所有邻接点，若不是父结点则递归调用 dfs(v, c ^ 1, u)（颜色翻转）。

主函数读入边后调用 dfs(1, 0, 0)（从 1 号结点开始，颜色为 0）。最后对于每个 ( i )，输出 cnt[bel[i]]。

时间复杂度分析

• 树有 ( n ) 个结点和 ( n-1 ) 条边，DFS 每个结点与每条边均被访问一次，复杂度为 ( O(n) )。
• 输出答案也是 ( O(n) )。
• 总时间复杂度 ( O(n) )，空间复杂度 ( O(n) )。对于 ( n \le 2 \times 10^5 ) 的数据范围完全可行。

参考代码

cpp
复制
1#include <cstdio>
2using namespace std;
3
4const int N = 2e5 + 5;          // 最大结点数
5const int E = N << 1;           // 双向边，最多 2*(n-1) 条边
6
7int n;
8int h[N], to[E], nx[E], et;     // 链式前向星存图
9int cnt[2];                     // cnt[0] 和 cnt[1] 分别记录两种颜色的结点数
10int bel[N];                     // 每个结点的颜色
11
12// 添加一条 u 到 v 的边
13void ae(int u, int v) {
14    et++;
15    to[et] = v;
16    nx[et] = h[u];
17    h[u] = et;
18}
19
20// 深度优先搜索染色并计数
21// u: 当前结点  c: 赋予的颜色  f: 父结点
22void dfs(int u, int c, int f) {
23    bel[u] = c;                 // 记录结点颜色
24    cnt[c]++;                   // 对应颜色计数增加
25    for (int i = h[u]; i; i = nx[i]) {
26        int v = to[i];
27        if (v != f)             // 避免向父结点回搜
28            dfs(v, c ^ 1, u);   // 子结点颜色取反
29    }
30}
31
32int main() {
33    scanf("%d", &n);
34    // 读入 n-1 条边
35    for (int i = 1; i < n; i++) {
36        int u, v;
37        scanf("%d%d", &u, &v);
38        ae(u, v);
39        ae(v, u);
40    }
41    // 从 1 号结点开始染色（颜色为 0）
42    dfs(1, 0, 0);
43    // 输出每个结点的答案
44    for (int i = 1; i <= n; i++)
45        printf("%d%c", cnt[bel[i]], " \n"[i == n]);
46    return 0;
47}

代码说明：

• " \n"[i == n] 是一个巧妙的输出格式控制：当 ( i = n ) 时取字符 '\n'，否则取空格，从而满足行末无多余空格的要求。
• c ^ 1 将颜色 0 变为 1，1 变为 0，实现颜色翻转。

总结

本题关键在于将“偶数步可达”的条件转化为二分图的同色结点问题。树天然是二分图，染色后同色结点的数量就是即便走了偶数步也只能在该集合内活动的结点总数。理解了这个性质之后，一次 DFS 即可轻松解决。