ARC153F 题解

First Post:

Last Update:

处理常规的图论题时，DFS 树，网络流等经典图论工具都能发挥作用，但这题提供了图论题的一个新思路：分析图中环、点双、边双的性质。（其实没有那么新，ZJOI 2022 D1T3 也是这么做的）

首先，”存在一条三种颜色的路径“难以考虑，不妨变为 ”原图有三种颜色“ 减去 ”原图有三种颜色但不存在三种颜色的路径“。

对于一个环，假设其上出现了三种颜色，那么有以下几种情况：

  1. 环长 ，此时显然无解，在环上肯定能找到一条三种颜色的路径。
  2. 环长 ，此时环上的边必须是三种不同的颜色，满足上述限制之后，还必须要求环上只有一个点有出边，设这个点为 ，环上不与 相连的那条边颜色为 ，那么环外的所有边颜色都必须是 。因此，这个环对方案数的贡献为 。如果有 个这样的环，这些环对方案的贡献都是独立的，所以贡献之和为 。

如果一个环上只有两种颜色，那么必然有一种颜色出现了两次及以上，不妨设颜色为 ，且 出现了多次。那么在环外找到一条颜色为 的边，并找到一个环上的点 使得从 出发能到达这条边，然后考虑环上 的邻边，如果都是 就删一条 ，否则删一条 ，将环的剩余部分与那条边串起来，就能找到一条三种颜色的路径。所以，一个环不可能只有两种颜色。

因为上文也处理了环上出现三种颜色的情况。所以剩下的情况中，环上都只有一种颜色，故可以缩点双建出圆方树。考虑在树上怎么填。事实上，对于一种合法方案，可以找到唯一的一个圆点 使得以 为根时，所有儿子子树颜色全部相同，且三种颜色都出现了，那么算方案时只需枚举这个点 ，其带来的贡献就只和儿子个数有关了，这容易计算。

注意，上文的证明都是基于 的，所以对于 的情况要暴力搜索解。

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
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5,P = 998244353;
inline void Plus(int &x,const int &y) { x += y;if(x >= P) x -= P;}
int n,m;
vector<pair<int,int> > G[N];

namespace Brute {
	const int N = 15;
	int col[N],ton[3];
	int now;
	bool vis[N];
	bool Check(int x) {
		vis[x] = 1;
		for(auto [y,i] : G[x]) {
			if(vis[y]) continue;
			now += !(ton[col[i]]++);
			if(now == 3 || Check(y)) return true;
			now -= !(--ton[col[i]]);
		}
		return vis[x] = 0;
	}
	int ans;
	void Dfs(int x) {
		if(x > m) {
			now = 0;
			for(int i = 1;i <= n;i++) 
				if(Check(i)) {
					memset(ton,0,sizeof ton);
					memset(vis,0,sizeof vis);
					++ans;break;
				}
			return;
		}
		col[x] = 0;Dfs(x + 1);
		col[x] = 1;Dfs(x + 1);
		col[x] = 2;Dfs(x + 1);
	}
}

int dfn[N],low[N],top,stk[N];
int dego[N]; // 每个圆点的出边数量

void tarjan(int x,int from) {
	dfn[x] = low[x] = ++dfn[0];
	stk[++top] = x;
	for(auto [y,i] : G[x]) {
		if(i == from) continue;
		if(!dfn[y]) {
			tarjan(y,i);
			low[x] = min(low[x],low[y]);
			if(low[y] >= dfn[x]) {
				while(stk[top] != y) ++dego[stk[top--]];
				++dego[y];++dego[x];--top;
			}
		}
		else low[x] = min(low[x],dfn[y]); 
	}
}
int Pow2[N],Pow3[N];
inline int F(int x) {
	if(x <= 2) return 0;
	return (Pow3[x] - 3ll * Pow2[x] % P + 3 + P) % P;
}
int main() {
	cin >> n >> m;
	for(int i = 1,u,v;i <= m;i++)
		cin >> u >> v,G[u].emplace_back(v,i),G[v].emplace_back(u,i);
	if(n <= 4) { Brute::Dfs(1);printf("%d\n",Brute::ans);return 0;}
	Pow2[0] = Pow3[0] = 1;
	for(int i = 1;i <= m;i++)
		Pow2[i] = (Pow2[i - 1] + Pow2[i - 1]) % P,
		Pow3[i] = 3ll * Pow3[i - 1] % P;
	int ans = 0;
	for(int u = 1;u <= n;u++)
		// if(G[u].size() >= 3)
		for(auto [v,i] : G[u]) {
			if(G[u].size() == 2 && G[v].size() == 2 && u < v) {
				int w = (G[u][0].first == v) ? G[u][1].first : G[u][0].first;
				if(w == ((G[v][0].first == u) ? G[v][1].first : G[v][0].first))
					Plus(ans,6);
			}
		}
	tarjan(1,0);
	for(int i = 1;i <= n;i++)
		Plus(ans,F(dego[i]));
	ans = (F(m) + P - ans) % P;
	cout << ans << endl;
	return 0;
}
≡