Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

[总结] 圆方树学习笔记

YoungNeal 2019-02-13 21:34:00 阅读数:165 评论数:0 点赞数:0 收藏数:0

圆方树

分为圆方树和广义圆方树。前者处理仙人掌,后者处理一般无向图。

只学了后一个。

广义圆方树

在无向图中进行\(\mathrm{Tarjan}\),对于每个点双构建一个方点,方点向点双中的所有点连边。

这就建好了一张新图。

对于一般的题,可以在圆点上维护这个点的信息,方点上维护这个点双的信息。这样就可以支持一些对无向图路径的操作了。

贴一张网上找来的图

观察一些性质:

  1. 圆点只能和方点相邻,同样的,方点只和圆点相邻。
  2. 如果两个方点有公共相邻的圆点,那这个圆点就是这两个方点代表的点双的割点。
  3. 还有很多但是我找不到了...

例题

[APIO2018] 铁人两项

Description

给定一张 \(n\) 个点 \(m\) 条边的无向图,请求出三元组 \((s,c,f)\) 的个数,使得存在一条从 \(s\)\(f\) 经过点 \(c\) 的简单路径。\(n,m\leq 2\cdot 10^5\)

Sol

先求出圆方树。

考虑枚举 \(s,f\),那么合法的 \(c\) 个数就是 \(s\)\(f\) 间的点双的点数和减去 \(s,f\) 这两个点。

设方点权值为点双的点数,圆点的权值为 \(-1\)

\(c\) 的数量就是 \(s,f\) 两点之间的点权和。

考虑枚举中点 \(c\),那点 \(c\) 的贡献就是经过 \(c\) 的路径数目*它的权值。

树形\(\mathrm{DP}\)即可

代码

[CF487E] Tourists

Description

给定一张 \(n\) 个点 \(m\) 条边的无向联通图,每个点有权值 \(w_i\)。要求支持:带修改,求两点之间所有路径上的最小权值。

Sol

如果不带修改怎么办?

还是求出圆方树。

把方点的点权设为点双中的最小权值,圆点权值即为本身的权值。

问题就变成了询问链上最小值。树剖即可。

加上修改呢?

如果还按照刚才的方法维护,假设一个点是割点,同时属于很多点双,那么在修改这个点的权值时,会顺便修改与它相连的所有方点的权值。如果这是个菊花图就卡掉了。

考虑一种套路,就是让每个点维护的信息少一点点,然后修改的复杂度就不那么大了,例子就是用\(\mathrm{lct}\)\(\mathrm{Qtree6}\)

这里也可以这样做,具体是让每个方点的权值不包含它的父亲(它的父亲肯定是圆点以及肯定在这个点双中),也就是说每个圆点的值只对圆方树上它的父亲有贡献。这样如果修改一个点的复杂度就降下来了。

那再回来考虑询问因为少维护了一些信息会出什么\(\mathrm{bug}\),发现就是当\(\mathrm{lca}\)为方点时,会少算这个方点的父亲的点权,特判一下就好了。

所以拿圆方树+树剖+\(\mathrm{mutiset}\)就可以解决本题了。

代码

版权声明
本文为[YoungNeal]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/YoungNeal/p/10371908.html

编程之旅,人生之路,不止于编程,还有诗和远方。
阅代码原理,看框架知识,学企业实践;
赏诗词,读日记,踏人生之路,观世界之行;

支付宝红包,每日可领