不如不见

dcytrl / 2025-02-21 / 原文

source：zr2024 二十联测

http://zhengruioi.com/contest/1717/problem/3061

题意

给定一棵以 $1$ 为根的树，树边有两种形态：实边和虚边。初始这棵树的所有边都为虚边。

定义 assert(x) 操作为：对于根到 $x$ 上所有点，将其与所有儿子的连边置为虚边，然后给根到 $x$ 这条链上的边置为实边。

给定一个最终树形态 $T$，问：有多少个排列 $P$，使得对初始树按顺序执行 $\operatorname{access}(P_i)$ 后最终树形态为给定的树形态。

初始 $T$ 全是虚边。$q$ 次操作，每次给定 $u$ 表示对 $T$ 执行 access(u) 后的答案。

$n,q\le 5\times10^5$

分析

考虑转换题意。

发现 1：对于树上的每条极长实链，实链链尾的操作时刻一定晚于实链上其他点的操作时刻。

发现 2：对于树上的每条极长实链，该实链链尾的操作时刻一定早于该实链链顶的父亲所属实链的链尾的操作时刻。

据此考虑一个经典做法：将所有非链底节点向所在实链的链底连边，链底节点向所属实链链顶的父亲所属实链的链底连边，则原图形成一棵树。问题转化为求一个排列使得 $P_{x}>P_{fa_x}$。

对这类问题有经典的树形 DP 做法，但可拓展性不高。实际上，该答案等于 $\dfrac{n!}{\prod siz'_i}$，证明可以通过类似多重排列数那样子的用组合意义证明。

这个式子还是不利于我们维护。考虑进一步转化：考虑到该式子在重构树上的组合意义，发现 $\dfrac{n!}{\prod siz'_i}=\dfrac{n!}{\prod_{i\in S}siz_i}$，其中 $S$ 为链顶集合，$siz_i$ 为原树子树大小（$siz'_i$ 为重构树子树大小）。

对于每一个实链链顶，其子树大小就等于其实链长度+实链上挂的其他子实链的长度之和。对于在其实链上的点（非链底），其在重构树上的 $siz'_i=1$；对于其余挂在实链上的子实链，其长度在重构树上都贡献给了链底。

那我们只需要快速维护 $S$ 的变化即可。由于 LCT 是十级算法，考虑树剖。对于每条重链，维护重链上所有链顶，对于一个 access 操作，其对重链的贡献就相当于将深度小于等于某个阈值的所有链顶删掉，并在阈值 +1 的深度上加入一个链顶。考虑用栈按深度从小到大的顺序维护，那么我们每次会弹出一段前缀，再压入一个元素。由于压入元素个数是 $O(n\log n)$ 级别的，故暴力弹出的复杂度也为 $O(n\log n)$。为了正确的维护，我们还要维护 $ron_i$ 表示 $i$ 的实儿子，若没有实儿子或实儿子是重儿子则 $ron_i=0$。$ron_i$ 也是好维护的。

综上，时间复杂度 $O(n\log n)$。