Tree(ICPC 2017 Shenyang)

简单结论题，评黄很合理吧。

结论：一个点与题目所求交集的边有公共部分，当且仅当以这个点为根时，存在两个不同儿子的子树大小 ≤k\le k，可以有一个子树包含该节点。

必要性大家都会证，如果不存在两个不同儿子的子树大小 ≤k\le k，那么这个点就一定没有任何相邻边被 kk 个颜色经过。接下来是充分性，感性理解一下，将不满足结论的点称作关键点，满足条件的，且与至少一个关键点相邻的非关键点称作临界点。将所有临界点（如果必须要【有一个子树包含该节点】，那么同时染上该临界点）所连的关键点子树染上 kk 种颜色，那么所有关键点的 sz≥ksz\ge k 的方向均至少存在一个临界点及其关键点子树染上了 kk 种颜色。构造成立。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void dfs(int u,int fa){
	sz[u]=1;
	int sum=0;
	for(auto v:E[u]){
		if(v==fa)continue;
		dfs(v,u);
		sum+=sz[v]>=m-1;
		sum+=sz[v]>=m-1&&n-sz[v]>=m; // 这里是【有一个子树包含该节点】的情况
		sz[u]+=sz[v];
	}
	sum+=(n-sz[u])>=m-1;
	sum+=(n-sz[u])>=m-1&&sz[u]>=m;
	if(sum>=2)++res;
}

环基基环树(SCCPC 2026)

你是？不就板子叠叠乐嘛，和 A 题坐一桌。

容易想到先把所有桥拆掉，注意到目前拆掉的所有桥都是原基环树上枝条的边。那么剩下的一堆边双剩下一个原基环树环和若干个基环树点。

可以通过判断边数和点数是否相等从若干个边双中找到这个原基环树上的环。现在关键是要拆环。如果你不想像其他题解一样再写一个并查集去缩点找环，那么你可以像我一样再写两遍 Tarjan。具体地，对于原环上的每一条边 (u,v)(u,v) 在新图，必然有 deg⁡u≥3,deg⁡v≥3\deg u\ge3,\deg v\ge3，但是注意到可能存在在一个点扩成的环上连续两个点都在原环上，所以不能直接根据 ⁡deg⁡⁡\deg 的性质特判。但是注意到只要是 deg⁡u≥3\deg u\ge 3 的点必然在原环上，所以随便找到一个 deg⁡≥3\deg\ge 3 的点拎出另外一个点 deg⁡≥3\deg\ge 3 的边判断一下断掉这条边剩下的部分是否还是一个大边双。若不是，断的就是原环边；若是，断的不是原环边。

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
void solve(){
	n=read(),m=read();
	idx=k=0;
	REP(i,1,n){
		E[i].clear();
		dfn[i]=low[i]=col[i]=sz[i]=0;
		cnt[i]=deg[i]=vis[i]=0;
	}
	REP(i,1,m){
		int u=read(),v=read();
		E[u].push_back(v);
		E[v].push_back(u);
	}
	tarjan(1,0);
	REP(u,1,n)for(auto v:E[u]){
		if(u>v||col[u]!=col[v])continue;
		++cnt[col[u]];
	} // 切割每一个边双
	p=0;
	REP(i,1,k)if(cnt[i]!=sz[i])p=i; // 通过判断点数边数是否一致找原环
	REP(i,1,n)if(col[i]==p)vis[i]=1;
	REP(u,1,n)for(auto v:E[u]){
		if(col[u]!=p||col[v]!=p||u>v)continue;
		++deg[u],++deg[v];
	}
	sz[p]=0;
	REP(u,1,n)for(auto v:E[u]){
		if(!p)break;
		if(!vis[u]||!vis[v])continue;
		if(deg[u]<3||deg[v]<3)continue; // 找到 deg>=3 的边
		U=min(u,v),V=max(u,v);
		if(check(u)){ // 判断剩下的是否是一个大边双
			REP(i,1,n)dfn[i]=low[i]=0;
			idx=0;
			tarjan3(u,0);
			break;
		}
	}
	writeln(k);
	REP(u,1,n)for(auto v:E[u]){
		if(col[u]==col[v]||u>v)continue;
		write_(col[u]),writeln(col[v]);
	}
}

彩蛋：Tunyu1s：写得一坨勾石。