题解：CF1527D MEX Tree

某模拟赛的 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)$。