虚树建树（单调栈法）
虚树建树（单调栈法）
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135266476
单调栈维护一条链，初始先按dfs序排序，考虑加入一个点
黑色为栈里面的点，红色为当前加入的点，蓝色为LCA点。
黄色部分需要全部pop掉，蓝色和红色要加入单调栈
代码见oi-wiki https://oi-wiki.org/graph/virtual-tree/
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-12-28
边分治+虚树+直径合并：P4220通道
边分治+虚树+直径合并：P4220通道 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135266426 https://www.luogu.com.cn/problem/P4220 第一棵树可以直接边分治，然后黑白染色，弄到第二棵树上建虚树 第三棵树很难搞。需要回到题目本身，发现题目没叫我们求奇奇怪怪的东西，而是求距离，肯定有啥性质，而且还是最大距离，就是一个点集的直径。 直径显然支持合并性，我们直接在虚树上树形dp进行合并即可 123456pre cod...
2023-12-28
边分治建虚树优化：P4565暴力写挂
边分治建虚树优化：P4565暴力写挂 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135272909 https://www.luogu.com.cn/problem/P4565 首先题目的式子很难看，可以变成 ： depx+depy+dis(x,y)−deplca2(x,y)2\frac {dep_x+dep_y+dis(x,y)-dep_{lca_2(x,y)}}2 2depx+depy+dis(x,y)−deplca2(x,y) 然后直接边...