同学们都会树的定义了吧,那么接下来我们来学习圆方树吧
圆方树
基础理论
圆方树,适用于仙人掌上问题,可将仙人掌转化为普通树。
将仙人掌上的点双连通分量合成一个方点(tarjan),剩余点作为圆点,其上做普通树处理即可。
(说起来很简单,来看一道例题吧!)
例题
简化题面:给出一张无向图, $ q(1<=q<=5e5) $ 次询问,每次询问给出两点,求两点路径上有多少个必须经过的点。
直接上圆方树,将圆点赋值为1,方点赋值为0,求路径和即可。
(据说树剖比倍增快)
(这道题用LCT的是魔鬼吧)
标签:方点,圆点,笔记,学习,圆方树,例题,仙人掌,赋值 From: https://www.cnblogs.com/T-water/p/16704481.html