先考虑 $|S| = 2$ 的情况:把原图缩成一棵圆方树,查询两点路径上的圆点个数(除去这两个点本身)。我们可以很方便的把这个性质拓展到 $|S|$ 为任意值的的情况,只要先差分出圆方树上每个点到根节点的圆点个数,然后把每次查询的点建出虚树,进行简单的树上差分即可。需要注意的是多组数据间的变量初始化,以及圆方树的节点个数是原来的两倍。
先考虑 $|S| = 2$ 的情况:把原图缩成一棵圆方树,查询两点路径上的圆点个数(除去这两个点本身)。我们可以很方便的把这个性质拓展到 $|S|$ 为任意值的的情况,只要先差分出圆方树上每个点到根节点的圆点个数,然后把每次查询的点建出虚树,进行简单的树上差分即可。需要注意的是多组数据间的变量初始化,以及圆方树的节点个数是原来的两倍。
圆方树可以解决仙人掌或一类无向图问题。
通过 tarjan 缩点双为方点,原来的点为圆点。每个圆点连边到自己所属的点双方点,跨点双的圆点连边转换为圆方点之间的连边。
参考代码:
1 | struct edge { |
由此我们可以发现一些有趣的性质:
又是一道非常水的黑题。给你一个双向图,你需要代替炎魔之王拉格纳罗斯(???)会净化图中的所有环,也就是除了链以外的强连通分量,成为一颗无根树。然后询问树上距离。
Update your browser to view this website correctly. Update my browser now