[CF1172E] Nauuo and ODT

[CF1172E] Nauuo and ODT

首先考虑单次询问，将每个颜色拉出来，求解有多少条路径至少包含一个给定点。

这就是维护所有黑色连通块的大小平方和。

我们每一次删掉一个点就等价于将所有和他相连的点删掉，这样一定会 T。

可以使用类似 CF487E Tourists 的套路，将其父亲—儿子化，如果一个点是黑色，那么就向他在树上的父亲连边，那么一个点所在联通块的大小就是 lct 上的大小减去 \(1\)。

不过对于根节点还需要一个父亲，所以再多添加一个点当他的父亲即可。

维护子树 siz 就是模板，那么我们就跳到该模板题：

[BJOI2014] 大融合

我们需要用 lct 维护动态加边删边下的子树大小。

具体的讲解在这里：https://www.luogu.com.cn/article/8c1adp79

反正只要虚链改变就一定要更新 siz2。