道路相遇 题目链接：luogu P4320 题目大意 给你一个无向连通图，无重边自环，然后每次给你两点，问你有多少个点是两点间路径必有的。 思路 圆方树pre模板题？ 圆方树怎么做这里不说，看铁人两项的博客。 …

https://atcoder.jp/contests/abc318/tasks/abc318_g 对原图建圆方树后，任意两点间的简单路径必然为其树上路径上方点对应其边双的点。 然后判断A，C路径上的方点是否会有B 圆方树： void dfs(int x) {dfn[x]low[x]tot; z.push(x); for(int …

题目链接 BZOJ 2125 最短路 圆方树 求一幅仙人掌图中，Q次询问两点最短路。 仙人掌问题，我们可以直接将原来的N个点缩点成为一棵生成树——圆方树。 这棵圆方树是怎样建立的呢，首先，我们看图： 这个是原图； 这…

Duathlon 铁人两项 题目链接：luogu P4630 题目大意 给你一个无向图，然后你可以按顺序选三个点 a,b,c，保证 a 可以到 b，b 可以到 c，而且存在方案使得这两个路径的交点只有 b。 然后问你有多少个满足的三元组。 思路…

P4630 [APIO2018] Duathlon 铁人两项 纯圆方树的模板，只要会建图，就会做 在求割点（或桥）的基础上 加一个缩点的操作就行，需要注意的是，一个割点可以同时属于多个点双，所以对割点要多次连边 #…

题意很简单，在仙人掌图上求两点的最短路。 做法：需要用到圆方树 先来看看什么是圆方树：圆方树，就是由仙人掌图转化而来，树上分两种点：圆点和方点，圆点是仙人掌图上的点，方点是由仙…

圆方树的定义 圆方树是用来解决仙人掌图的问题的，那什么是仙人掌图呢？ 即不存在边同时属于多个环的无向连通图是一棵仙人掌。 点双连通分量的定义 要介绍圆方树，首先要介绍点双连通分量。 一个点双连通图的一个定义是：图中任…

所谓圆方树，就是又圆又方的树 （逃） 前言 树有很多良好的性质，也可以上许多算法和数据结构 但我们对于一般图却没有太多办法… 然而，对于有些关注连同性、路径并&交的一般图问题，我们可以用圆方树&…