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

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

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

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

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

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

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

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

#include<bits/stdc++.h>
#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;
}