先考虑 $|S| = 2$ 的情况:把原图缩成一棵圆方树,查询两点路径上的圆点个数(除去这两个点本身)。我们可以很方便的把这个性质拓展到 $|S|$ 为任意值的的情况,只要先差分出圆方树上每个点到根节点的圆点个数,然后把每次查询的点建出虚树,进行简单的树上差分即可。需要注意的是多组数据间的变量初始化,以及圆方树的节点个数是原来的两倍。

圆方树学习笔记

圆方树可以解决仙人掌或一类无向图问题。

建树

通过 tarjan 缩点双为方点,原来的点为圆点。每个圆点连边到自己所属的点双方点,跨点双的圆点连边转换为圆方点之间的连边。

参考代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
struct edge {
int tot, flag, hed[N], nxt[M], to[M];
edge () { tot = 2; }
void link(int u, int v) {
nxt[tot] = hed[u], to[tot] = v, hed[u] = tot++;
nxt[tot] = hed[v], to[tot] = u, hed[v] = tot++;
}
} G1, G2;

void tarjan(int u, int father) {
++base, dfn[u] = low[u] = ++tim, ins[u] = 1, stk[++top] = u;
for (int i = G1.hed[u], v = G1.to[i]; i; i = G1.nxt[i], v = G1.to[i])
if (v != father) {
if (!dfn[v]) {
tarjan(v, u), low[u] = std::min(low[u], low[v]);
if (low[v] >= dfn[u]) {
G2.link(u, ++tot), ++val[tot]; int x;
do {
x = stk[top--], ins[x] = 0;
G2.link(x, tot), ++val[tot];
} while (x != v);
}
} else if (ins[v]) low[u] = std::min(low[u], dfn[v]);
}
}
  • 需要注意的是,根节点所在的点双的方点并不会创建,在大多数情况下,这并不会有影响,可根据题目的需要取舍。

性质

由此我们可以发现一些有趣的性质:

  • 现在总点数与原来的点数同阶,现在的总边数与原来的总边数同阶
  • 所有边都是圆点和方点之间的连边,即不存在圆圆边或方方边

又是一道非常水的黑题。给你一个双向图,你需要代替炎魔之王拉格纳罗斯(???)会净化图中的所有环,也就是除了链以外的强连通分量,成为一颗无根树。然后询问树上距离。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×