题目理解

我们有一棵 $n$ 个节点的树，每个节点（城市）有罢工状态。当城市罢工时，该城市无法通行。需要动态维护非罢工城市形成的连通分量数量。

关键观察

1. 树的性质

• 初始时所有城市连通（1个连通分量）
• 当城市罢工时，会断开与相邻城市的连接
• 罢工城市本身不计入连通分量

2. 连通分量变化规律

对于树上的一个节点 $x$：

• 当 $x$ 从非罢工变为罢工时：
  • 断开与所有非罢工子节点的连接
  • 断开与父节点的连接（如果父节点非罢工）
• 当 $x$ 从罢工变为非罢工时：
  • 恢复与所有非罢工子节点的连接
  • 恢复与父节点的连接（如果父节点非罢工）

算法核心

动态维护连通分量数量

设当前连通分量数量为 ans，初始为 1（所有城市连通）。

预处理

void dfs(int x, int f) {
    fa[x] = f;  // 记录父节点
    for (auto v : g[x]) {
        if (v == f) continue;
        cs[x]++;  // 记录子节点数量
        dfs(v, x);
    }
}

罢工操作（p > 0）

ans += cs[x];        // 每个非罢工子节点都会形成新的连通分量
if (fa[x]) {
    if (on[fa[x]])   // 如果父节点非罢工
        ans++;       // 父节点方向也会形成新的连通分量
    cs[fa[x]]--;     // 父节点减少一个子节点
}
on[x] = 0;           // 标记为罢工
ans--;               // 当前节点不再属于任何连通分量

结束罢工操作（p < 0）

ans++;               // 当前节点重新加入
ans -= cs[x];        // 重新连接所有非罢工子节点
if (fa[x]) {
    if (on[fa[x]])   // 如果父节点非罢工
        ans--;       // 与父节点合并连通分量
    cs[fa[x]]++;     // 父节点增加一个子节点
}
on[x] = 1;           // 标记为非罢工

算法正确性

1. 初始状态

• 所有城市非罢工 (on[i] = 1)
• 连通分量数量 ans = 1

2. 罢工操作分析

当城市 $x$ 罢工时：

• cs[x]：$x$ 的非罢工子节点数量，每个都会形成独立连通分量
• 如果父节点非罢工：父节点方向也会形成新的连通分量
• 减去 $x$ 本身：罢工城市不计入连通分量

3. 结束罢工分析

当城市 $x$ 结束罢工时：

• 加上 $x$ 本身：重新成为一个连通分量
• 减去 cs[x]：与所有非罢工子节点合并
• 如果父节点非罢工：与父节点合并连通分量

时间复杂度

• DFS预处理：$O(n)$
• 每次操作：$O(1)$
• 总复杂度：$O(n + m)$

在 $n, m \leq 5 \times 10^5$ 的限制下完全可行。

关键数据结构

1. 邻接表：g[N] 存储树结构
2. 父节点数组：fa[N] 记录每个节点的父节点
3. 子节点计数：cs[N] 记录每个节点的非罢工子节点数量
4. 罢工状态：on[N] 标记节点是否在罢工

算法优势

1. 增量更新：每次操作只更新局部信息
2. 常数时间：每个操作 $O(1)$ 完成
3. 空间高效：只使用简单数组
4. 在线处理：支持实时查询

特殊情况处理

根节点处理

根节点没有父节点，所以不需要检查 fa[1]

所有城市罢工

当所有城市都罢工时，ans 会递减到 0，符合题目要求

算法标签

• 树形结构
• DFS
• 连通分量
• 增量更新

总结

该算法通过巧妙的计数维护，在树形结构上高效动态计算连通分量数量。核心思想是利用树的父子关系，通过局部更新反映全局变化，实现了 $O(1)$ 每次操作的高效算法。设计简洁而精妙，充分体现了树形结构问题的特性。