【学习笔记】[ARC153F] Tri-Colored Paths

假设三种颜色的边都存在，并且不存在这样的路径

首先观察到，对于一个简单环上的边，颜色一定相同

因此，考虑建立圆方树，问题转化为圆方树上的$DP$问题。限制是对于方点所连接的边，必须涂上相同的颜色，也就是不存在一条路径上有三种颜色的方点

注意到，如果有两个相邻的颜色不同的方点，那么其对应的子树内的方点一定只有一种颜色。又因为三种颜色的方点都出现过，因此将圆点删除后，剩下的连通块内方点也一定只有一种颜色。考虑到圆方树的性质：只有方点和圆点有边相连，因此枚举这个圆点并统计答案即可。

需要注意的是，当$n\le 4$时需要暴搜解决。这是因为环上会出现反例。同理，对于大小为$3$的点双也要特判（环上的点颜色互不相同，出边只有一条，其他边的颜色都和环上某一条边的颜色相同）。

复杂度$O(n+m)$。

$\text{remark}$ 对于圆方树上的$DP$问题，分析性质有时候比设计状态更重要。

#include
#define ll long long
#define pb push_back
#define fi first
#define se second
#define db double
#define ull unsigned long long
#define inf 0x3f3f3f3f
using namespace std;
const int mod=998244353;
const int N=2e5+5;
int n,m,cnt;
int dfn[N],low[N],du[N],num;
vector<int>G[N];
stack<int>s;
ll res;
ll fpow(ll x,ll y=mod-2){
    ll z(1);
    for(;y;y>>=1){
        if(y&1)z=z*x%mod;
        x=x*x%mod;
    }return z;
}
vector<int>vec[N];
void tarjan(int u){
    dfn[u]=low[u]=++num,s.push(u);
    for(auto v:G[u]){
        if(!dfn[v]){
            tarjan(v),low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u]){
                int tmp=0;du[u]++,cnt++;
                do{
                    tmp=s.top(),s.pop();
                    du[tmp]++,vec[cnt].pb(tmp);
                }while(tmp!=v);vec[cnt].pb(u);
            }
        }else low[u]=min(low[u],dfn[v]);
    }
}
void add(ll &x,ll y){
    x=(x+y)%mod;
}
vector<pair<int,int>>edge;
int w[10][10],p[10];
void dfs(int x){
    if(x==m){
        int ok=0;
        for(int i=1;i<=n;i++)p[i]=i;
        do{
            int sz=0;
            for(int i=2;i<=n;i++){
                if(~w[p[i]][p[i-1]]){
                    sz|=1<<w[p[i]][p[i-1]]-1;
                    if(sz==7)break;
                }else break;
            }if(sz==7){
                ok=1;
                break;
            }
        }while(next_permutation(p+1,p+1+n));
        res+=ok;
        return;
    }int u=edge[x].fi,v=edge[x].se;
    for(int i=1;i<=3;i++){
        w[u][v]=w[v][u]=i,dfs(x+1);
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y;cin>>x>>y;
        G[x].pb(y),G[y].pb(x),edge.pb({x,y});
    }
    if(n<=3){
        cout<<0;
        return 0;
    }
    if(n==4){
        memset(w,-1,sizeof w),dfs(0);
        cout<<res;
        return 0;
    }
    for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
    res=(fpow(3,m)-3*fpow(2,m)+3)%mod;
    for(int i=1;i<=n;i++){
        if(du[i]>=3){
            add(res,-fpow(3,du[i])+3*fpow(2,du[i])-3);
        }
    }
    for(int i=1;i<=cnt;i++){
        if(vec[i].size()==3){
            int tot=0;
            for(auto e:vec[i])if(du[e]>1)tot++;
            if(tot<=1)add(res,-6);
        }
    }
    cout<<(res+mod)%mod;
}
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