Luogu6556 The Forest

题意：有 个灯泡，用红色边连成一棵红色树，再用蓝色边连成一棵蓝色树。

问有多少个灯泡的子集，在红色树上形成连通块，在蓝色树上形成一条链。

多组数据，，，时限 。

---

• 前置知识：换根子树加。

• 引理：树上点集形成的连通块数目 点数 内部边数。

• 推论：树上点集形成连通块 点数 边数 。

类似于序列扫描线，考虑换根：（蓝树）记当前根为 ，维护数组 ，表示蓝路径 是否在红树上形成连通块。类似序列扫描线，换根并考虑 的变化。

记 为路径 是红树上形成连通块数目，等于点数减内部边数。。考虑如何维护 。

假设根从 换到相邻的点 ，那么：

• 侧的点 ：蓝路径减少了点 ；
• 侧的点 ：蓝路径增加了点 。

点数的变化是两个子树加减，容易处理。

考虑边的变化，对于添加了点 的 侧，枚举 在红树上的所有邻居 ，查看边 对那些集合有贡献，也就是蓝路径包含 的集合，可以发现，那是 的子树，所以子树减即可。另一侧的处理方法类似。

暴力枚举的复杂度是红度数 蓝度数，无法承受。可以发现，每个红邻居只会有一次有用，而通过蓝 dfs 序可以快速筛选出有用的邻居。（细节略）

在对 区间加减的同时，容易维护 的和（维护最小值个数即可）。

复杂度 。