「春季大扫除」题解

问题分析

我们有一棵 $N$ 个节点的树，每次操作可以添加若干叶子节点，需要求出清理新树的最小费用。清理规则是：每次选择两个叶子节点，清理它们路径上的所有边，费用为路径长度，每个叶子最多被选一次。

关键观察

1. 可行性条件

设改造后树的叶子节点总数为 $L$，则：

• 必要条件：$L$ 必须为偶数，否则输出 $-1$
• 因为每次清理需要一对叶子节点

2. 费用计算

对于任意树，设叶子节点集合为 $S$，最小清理费用为：

$$\text{cost} = \sum_{e \in E} \max(1, \text{覆盖次数}_e) $$

其中 $\text{覆盖次数}_e$ 表示边 $e$ 被路径覆盖的次数。

核心算法

1. 度数与奇偶性分析

设节点 $u$ 的度数为 $\deg(u)$，定义：

$$f(u) = \begin{cases} 1 & \text{if } \deg(u) = 1 \ (\text{叶子节点}) \\ 0 & \text{otherwise} \end{cases} $$

添加叶子节点后，节点 $u$ 的度数变化：

$$\deg'(u) = \deg(u) + \text{cnt}[u]$$

其中 $\text{cnt}[u]$ 是在 $u$ 上添加的叶子节点数。

新的叶子节点数：

$$L = \sum_{u=1}^N [\deg'(u) = 1]$$

2. 树形DP预处理

设 $dp[u]$ 表示以 $u$ 为根的子树中，需要向上延伸的路径条数。

状态转移：

• 对于叶子节点：$dp[u] = 1$（有一条路径需要向上延伸）
• 对于非叶子节点：$dp[u] = \left(\sum_{v \in \text{children}(u)} dp[v]\right) \bmod 2$

费用计算：

• 如果 $dp[v] = 1$，则边 $(u,v)$ 被覆盖1次
• 如果 $dp[v] = 0$，则边 $(u,v)$ 被覆盖2次（因为路径在子树内匹配完成）

总费用：

$$\text{base\_cost} = \sum_{(u,v) \in E} \begin{cases} 1 & \text{if } dp[v] = 1 \\ 2 & \text{if } dp[v] = 0 \end{cases} $$

3. 添加叶子节点的影响

当在节点 $u$ 上添加 $k$ 个叶子时：

• 如果 $\deg(u) = 1$，添加后 $u$ 不再是叶子，叶子数变化：$-1 + k$
• 如果 $\deg(u) > 1$，添加后 $u$ 仍不是叶子，叶子数变化：$+k$

度数变化对DP值的影响：

• 添加叶子节点相当于改变了节点 $u$ 的奇偶性
• 需要重新计算从 $u$ 到根的路径上的DP值

4. 快速计算算法

预处理：

1. 以任意节点（如1）为根，计算初始的DP值
2. 计算每个节点到根的路径异或和
3. 预处理子树信息

查询处理： 对于每次添加 $D$ 个叶子节点到位置 $a_1, a_2, \ldots, a_D$：

1. 计算新的叶子数：

   $$L_{\text{new}} = L_{\text{orig}} + \sum_{i=1}^D \Delta_i $$

   其中 $\Delta_i = \begin{cases} \text{cnt}[a_i] - 1 & \text{if } \deg(a_i) = 1 \\ \text{cnt}[a_i] & \text{otherwise} \end{cases} $

2. 判断可行性：

   • 如果 $L_{\text{new}}$ 为奇数，输出 $-1$

3. 计算费用变化： 添加叶子节点会翻转从添加位置到根的路径上所有边的覆盖次数：

   $$\Delta_{\text{cost}} = \sum_{u \in \text{affected\_path}} (2 - 2 \times \text{current\_cover}[u]) $$

   其中 $\text{current\_cover}[u]$ 是当前边被覆盖的次数（1或2）

时间复杂度分析

• 预处理：$O(N)$
• 每次查询：$O(D + \text{影响的路径长度})$
• 总复杂度：$O(N + Q + \sum D_i)$

由于 $\sum D_i \leq 10^5$，该算法可以高效处理大规模数据。

正确性证明

1. 可行性：叶子数为偶数是完全清理的必要充分条件
2. 最优性：每条边至少被覆盖1次，最多被覆盖2次。当子树内路径能匹配完成时，边被覆盖2次；否则需要向上延伸，边被覆盖1次
3. 费用最小：最小化向上延伸的路径数，即最大化子树内匹配