[HNOI2014]世界树

[HNOI2014]世界树

建立虚树

子树外的点的处理很麻烦

考虑怎么找

首先对虚树上的点找到控制它的点的编号

f[i],g[i]往里,往外的最近距离,类似换根,还要记录pr,bc前兄弟后兄弟的前缀f值,还要记录方案

发现对于虚树的边,只有两头的点才回“争夺”边的控制权和边下边一堆子树的控制权

对于一条边

如果两端所属编号相同,就是这条边自己了

如果不同,倍增找到中间的位置,然后各居一半

最后dfs自底向上更新答案

我的更新答案的方式是:

边上点的sz减去子树里统计过的总的sz

对于绿色的部分控制范围就这样统计

注意:

1.清空虚树上所有的点,包括LCA

2.点之间的边还要考虑两点可能不是出发点(是LCA),延伸距离还要考虑控制点到两个点自己的距离。

3.虚树建立时候可能LCA会算重注意。

原文地址:https://www.cnblogs.com/Miracevin/p/10383700.html