题解：CF1527D MEX Tree

Aegleseeker_ · 2025-09-07 15:28:16 · 题解

某模拟赛的 T1。

一个 k 的答案为经过点集 0,1,\dots,k-1 但不经过点 k 的路径条数。令 f_i 为经过点集 0,1,\dots,i 的路径条数，则答案为 f_{k-1}-f_k。考虑从小到大枚举求出 f_i 即可。可以动态维护当前点集的虚树结构，但没什么必要。注意到一个点集有贡献当且仅当它在虚树上形成一条路径，因此我们只需要按「祖链」、「两条链拼起来」两种情况分类讨论即可，分别维护虚树路径的两个端点即可（对于祖链维护深度最大最小的两点，对于两条链分别维护两个端点），分讨中需要求 \text{lca}，复杂度 O(n\log n)。