$P11962$ [$GESP202503$ 六级] 树上漫步 题解

题目分析

本题需要计算树上每个结点经过偶数步能到达的结点数量。关键点在于：

• 偶数步结束：最终步数必须为偶数（包括 $0$ 步）
• 结点可达性：可以重复访问结点，但结束位置必须满足步数为偶数
• 树上特性：在树结构中，结点间路径唯一

核心思路：奇偶性分析

• 深度奇偶性：以任意结点为根计算深度，将结点分为两类（深度奇/偶）
• 路径奇偶性：两个结点间路径长度的奇偶性取决于它们深度奇偶性是否相同
  • 同奇偶性 → 路径长度为偶数
  • 不同奇偶性 → 路径长度为奇数
• 可达条件：从起点 $u$ 到终点 $v$ 可达的条件是存在一条长度为偶数的路径

算法实现

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    vector<vector<int>> graph(n+1);
    
    // 构建树结构
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    
    // BFS计算深度
    vector<int> depth(n+1, -1);
    queue<int> q;
    depth[1] = 0;
    q.push(1);
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : graph[u]) {
            if (depth[v] == -1) {
                depth[v] = depth[u] + 1;
                q.push(v);
            }
        }
    }
    
    // 统计深度奇偶性结点数
    int cnt0 = 0, cnt1 = 0;
    for (int i = 1; i <= n; i++) {
        if (depth[i] % 2 == 0) cnt0++;
        else cnt1++;
    }
    
    // 输出结果
    for (int i = 1; i <= n; i++) {
        if (depth[i] % 2 == 0) 
            cout << cnt0 << " ";
        else 
            cout << cnt1 << " ";
    }
    
    return 0;
}

算法解析

$1$. 树结构构建

• 使用 $vector$ 邻接表存储树
• 时间复杂度：$O(n)$

$2$. $BFS$遍历

• 以结点 $1$ 为根节点
• 计算每个结点的深度
• 时间复杂度：$O(n)$

$3$. 奇偶性统计

• $cnt0$：深度为偶数的结点数
• $cnt1$：深度为奇数的结点数

$4$. 结果输出

• 对于深度为偶数的结点，输出 $cnt0$
• 对于深度为奇数的结点，输出 $cnt1$

正确性证明

1. 可达性等价：
   • 从结点 $u$ 出发，能到达的结点 $v$ 需满足 $depth[u]$ 和 $depth[v]$ 奇偶性相同
2. 充分性：
   • 相同奇偶性 → 存在偶数长度路径
3. 必要性：
   • 不同奇偶性 → 所有路径长度均为奇数

复杂度分析

指标	值	说明
时间复杂度	$O(n)$	$BFS$ 遍历和统计均为线性时间
空间复杂度	$O(n)$	邻接表和深度数组空间占用

示例验证

输入$1$：

3
1 3
2 3

计算过程：

1. 以结点 $1$ 为根：
   • depth[1]=0 (偶)
   • depth[3]=1 (奇)
   • depth[2]=2 (偶)
2. 统计：
   • cnt0 = 2 (结点 $1$,$2$)
   • cnt1 = 1 (结点 $3$)
3. 输出：
   • 结点 $1$(偶) → $2$
   • 结点 $2$(偶) → $2$
   • 结点 $3$(奇) → $1$

输出$1$：

2 2 1

输入$2$：

4
1 3
3 2
4 3

计算过程：

1. 以结点 $1$ 为根：
   • depth[1]=0$ (偶)
   • $depth[3]=1$ (奇)
   • depth[2]=2 (偶)
   • depth[4]=2 (偶)
2. 统计：
   • cnt0 = 3 (结点 $1$,$2$,$4$)
   • cnt1 = 1 (结点 $3$)
3. 输出：
   • 结点 $1$(偶) → $3$
   • 结点 $2$(偶) → $3$
   • 结点 $3$(奇) → $1$
   • 结点 $4$(偶) → $3$

输出$2$：

3 3 1 3

该解法充分利用了树的特性和奇偶性分析，以线性时间复杂度高效解决问题。