【仙人掌学习笔记】二、圆方树——变仙人掌为树的艺术

Posted on | In |
Words count in article: 832 | Reading time ≈ 3

近年来，仙人掌在各大OI竞赛中的出现逐渐频繁，虽然仙人掌本身就有一些特殊而优美的性质，但我们终究是没有很多针对仙人掌的算法，就使得很多仙人掌的题变得很棘手。

那么真的没有办法快速解决仙人掌上的问题吗？不不不，我们可以想到的是，如果把仙人掌变成一棵树，那么我们学的大量的树上算法就有了用武之地。那么怎么做呢？我在这里介绍一种优美的方法：使用圆方树。

所谓圆方树，顾名思义，就是有圆点和方点的树。我们假设原图的点都为圆点，方点则是新加入的点，对于每一个点双，我们都会新加入一个方点。

同时，为了使圆方树成为一棵树，我们要断掉原来点双之间的边，相应的，每一个点双中的圆点都要和对应的方点连一条边。这样每个点双中都由n个点变为了n+1个点，同时有n个圆点，就有n条边，也就可以保证新图是一棵树了。

举个例子，下图就是一棵仙人掌：

然后建成圆方树之后就变成了这样：

圆方树有这些优美的性质：

  1. 无论如何换根，圆方树形态不变
  2. 圆方树的子树=原仙人掌的子仙人掌
  3. 方点不会和方点相连

在代码实现方面，求点双的方法在本系列第一篇文章【仙人掌学习笔记】一、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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
struct Graph
{
	int head[N],cnt;
	struct edge
	{
		int to,nxt,weight;
	};
	edge e[N];
	Graph()
	{
		memset(head,-1,sizeof(head));
		cnt=-1;
	}
	void add_edge(int u,int v,int w)
	{
		e[++cnt]=(edge){v,head[u],w};
		head[u]=cnt;
	}
	void Insert(int u,int v,int w)
	{
		add_edge(u,v,w);
		add_edge(v,u,w);
	}
};
Graph G,T;
il int findf(int x)
{
	return x==father[x]?x:father[x]=findf(father[x]);
}
il void ClearStack(int x)
{
	BCC_num++;
	int tot=0;
	do{
		int ed=st[top];
		int v=G.e[ed^1].to;
		bel[v]=BCC_num;
		len[BCC_num]+=G.e[ed].weight;
		cur[v]=len[BCC_num];
		if(dfn[v]<dfn[rt[BCC_num]])
			rt[BCC_num]=v;
		tmp[++tot]=v;
	}while(st[top--]!=x);
	for(ri i=1;i<=tot;i++)
	{
		int t=abs(cur[tmp[i]]-cur[rt[BCC_num]]);
		dis[tmp[i]]=min(t,len[BCC_num]-t);
		zip[tmp[i]]=(dis[tmp[i]]==t);
		if(tot>1)
		{
			T.Insert(tmp[i],n+BCC_num,dis[tmp[i]]);
			int findx=findf(tmp[i]),findy=findf(n+BCC_num);
			if(findx!=findy)
				father[findx]=findy;
		}
	}
}
il void Tarjan(int x,int pre)
{
	dfn[x]=low[x]=++id;
	int child=0;
	for(ri i=G.head[x];~i;i=G.e[i].nxt)
	{
		int v=G.e[i].to;
		if(vis[i]||v==pre)
			continue;
		st[++top]=i;
		vis[i]=vis[i^1]=1;
		if(!dfn[v])
		{
			child++;
			Tarjan(v,x);
			low[x]=min(low[x],low[v]);
			if((x==pre&&child>1)||(x!=pre&&low[v]>=dfn[x]))
				ClearStack(i);
		}
		else
			low[x]=min(low[x],dfn[v]);
	}
}
int main()
{
	read()
	for(ri i=1;i<=n*2;i++)
		father[i]=i;
	dfn[0]=inf;
	Tarjan(1,1);
	if(top)
		ClearStack(st[1]);
	for(ri u=1;u<=n;u++)
		for(ri i=G.head[u];~i;i=G.e[i].nxt)
		{
			int v=G.e[i].to;
			int findx=findf(u),findy=findf(v);
			if(findx!=findy)
			{
				T.add_edge(u,v,G.e[i].weight);
				father[findx]=findy;
			}
		}
	return 0;
}

0%