v 能被 u 控制的条件跟 av 有关而跟 au 无关。
所以我们可以针对这个 v 解题。
很显然的暴力:枚举这个 v,并从他开始一直往上找祖先,直到一个祖先无法控制它,v 对这中间这一段的答案都有贡献。
发现单调性。
所以有了树上倍增。
统计答案就树上差分覆盖这中间这一段。
代码:
1 |
|
v 能被 u 控制的条件跟 av 有关而跟 au 无关。
所以我们可以针对这个 v 解题。
很显然的暴力:枚举这个 v,并从他开始一直往上找祖先,直到一个祖先无法控制它,v 对这中间这一段的答案都有贡献。
发现单调性。
所以有了树上倍增。
统计答案就树上差分覆盖这中间这一段。
代码:
1 | #include <cstdio> |
Related Issues not found
Please contact @Alpha1022 to initialize the comment