ARC153F 题解

DaiRuiChen007 · 2024-04-20 21:18:35 · 题解

Problem Link

题目大意

给定一张 n 个点 m 条边的无向简单连通图，求有多少种给边染色 \{1,2,3\} 的方法，使得至少存在一条简单路径上有三种颜色。

数据范围：n,m\le 2\times 10^5。

思路分析

注意到限制比较松，我们可以考虑染了三种颜色但没有这样路径的方案数。

先考虑树的情况，取某条极长路径 u\to v，显然路径上只有两种颜色，不妨假设第三种颜色在树上某个点 w 子树内。

那么 u\to w 整个部分不能包括两种颜色，同理 w\to v 部分也只能有一种颜色。

因此我们还能证明这样的 w 至多一个。

方案数就是 \sum f(deg_u)，其中 f(x)=3^x-3\times 2^x+3。

因此对于一棵树，合法的染色方案一定存在恰好一个节点，使得该节点每个子树内都染相同颜色。

然后考虑一般情况，先缩点，对每个点双联通分量内部讨论：

• 存在一个长度 \ge 4 的环，此时整个点双联通分量只能染同一颜色，否则必然存在一条路径从任意一个点出发经过两种颜色，此时这个点往外连第三种颜色即可（手玩可以得出结论）。
• 否则该点双连通分量中只有三元环，先假设每条边颜色各不相同：
  • 手玩发现如果环上存在两个点 u,v ，以及环外两点 x,y 使得 x\to u,y\to v 存在（x\ne y）那么这个环不能染 > 1 种颜色。
  • 否则分类讨论：如果 u,v,w 都只和 \le 1 个环外点相连，那么此时三元环可以染三种颜色，然后环外边染该点在环上对边的颜色，恰有 6 种方案，这种情况只在 n=4,m\ge 5 时出现。
  • 否则这个点双一定恰为三元环，且恰有一个点 u 向外连边（假设 n>3），手玩发现三元环必须染三种不同颜色，且环外所有边必须都染 u 对边颜色，也只有 6 种方案。

否则所有点双都同色，类似树的结论，可以在圆方树上恰取出一个圆点使得其每个子树染相同颜色。

答案还是 \sum f(deg_u)，但 u 是圆方树上所有圆点。

时间复杂度 \mathcal O(n+m)。

代码呈现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=2e5+5,MOD=998244353;
vector <int> G[MAXN],C[MAXN];
int n,m,stk[MAXN],tp,dcnt,sc,dfn[MAXN],low[MAXN],d[MAXN];
ll ksm(ll a,ll b,ll p=MOD) {
    ll ret=1;
    for(;b;a=a*a%p,b>>=1) if(b&1) ret=ret*a%p;
    return ret;
}
void tarjan(int u,int fz) {
    dfn[u]=low[u]=++dcnt,stk[++tp]=u;
    for(int v:G[u]) if(v^fz) {
        if(!dfn[v]) {
            tarjan(v,u),low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u]) {
                int k;
                C[++sc].push_back(u),++d[u];
                do k=stk[tp--],C[sc].push_back(k),++d[k];
                while(k!=v);
            }
        } else low[u]=min(low[u],dfn[v]);
    }
}
signed main() {
    scanf("%d%d",&n,&m);
    for(int i=1,u,v;i<=m;++i) {
        scanf("%d%d",&u,&v);
        G[u].push_back(v),G[v].push_back(u);
    }
    tarjan(1,0);
    ll ans=0;
    if(n==4&&m>=5&&sc==1) ans+=6;
    for(int i=1;i<=n;++i) if(d[i]>=3) ans+=ksm(3,d[i])-3*ksm(2,d[i])+3;
    for(int i=1;i<=sc;++i) if(C[i].size()==3) {
        if((d[C[i][0]]>1)+(d[C[i][1]]>1)+(d[C[i][2]]>1)<=1) ans+=6;
    }
    printf("%lld\n",((ksm(3,m)-ans-3*ksm(2,m)+3)%MOD+MOD)%MOD);
    return 0;
}