ABC329G Solution

irris · 2023-11-19 13:56:02 · 题解

要求每条边经过恰好两次，实质上相当于 DFS 整棵树。那么不同的遍历方案就相当于需要 安排每个儿子数恰好为 \boldsymbol 2 的顶点的儿子 DFS 顺序。

确定了遍历顺序后，对答案的统计是容易的：先判断对每个 s_i 都能走到 t_i，然后进行区间加，判断全局最大值是否不超过 k。

考虑这个过程中，每条边被遍历次数的下界。显然对每个 s_i \to t_i 路径，仅有路径上的边一定会被遍历次数 +1（注意 x \to y 和 y \to x 不是同一时刻被遍历的边，自然 不被视作是同一条边；(u, v) 实际的被遍历次数的最大值是向上次数和向下次数的较大值，而非和）。对于某特定的遍历顺序，我们将其路径拆分为两段：

这是以子树为单位的遍历次数增加；考虑将子树内每条边被遍历次数的最大值记录入状态，则发现这个信息是可以从下向上合并的。

可以预处理增加量：设 c_1(i) 表示若 i 是第一个被遍历的儿子，则其兄弟的子树得到的增加量，c_2(i) 同理。c 可以直接用树上差分计算。

此时直接 DP 即可：令 dp_{i,j} 计数，仅考虑点 i 的子树内，边最大被遍历次数等于 j 的方案数。

• 若点 i 为叶子，那么 dp_{i, L_i} = 1。
• 若点 i 有且仅有一个儿子 u，那么 dp_{i,\max(L_i, j)} \gets^+ dp_{u,j}。
• 若点 i 有两个儿子 u, v。枚举哪个是第一个遍历的，不失一般性设为 u，剩余情况对称：
  • 枚举其中一个量，对另一个做前缀和即可 O(K) 转移。

还需要考虑一个细节：对于一个 s \to t 的 非祖先-后代链 要求，这本质上已经要求了 \operatorname{lca}(s, t) 的两个儿子 DFS 顺序固定，否则必然不能从 s 走到 t。在求 LCA 的过程中额外记录一下即可。

时间复杂度 O((N+M)\log N + NK)。