您好,欢迎来到保捱科技网。
搜索
您的当前位置:首页[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

因篇幅问题不能全部显示,请点此查看更多更全内容

Copyright © 2019- baoaiwan.cn 版权所有 赣ICP备2024042794号-3

违法及侵权请联系:TEL:199 18 7713 E-MAIL:2724546146@qq.com

本站由北京市万商天勤律师事务所王兴未律师提供法律服务