AT_arc153_f 题解

· · 题解

考虑将“用三种颜色染色”的方案数减去“用了三种颜色，然而不存在任何一条有三种颜色的路径”的方案数以得出答案。

  1. 考虑某个环有三种颜色的情况：

    1. 环的大小 \ge 4。此时一定可以找出一条至少出现了两次的边，剩下的边可以组成一条路径且包含了三种颜色。

    2. 该环为三元环（令这三个点为 u,v,w）。考虑其向其他点连的边的情况。

      1. 如果环上存在两个点 u,v 均向其他点连边。如果 u 和 v 均连向了同一个点 x；则由路径 x-u-w-v 和 x-u-v-w 存在可得 x-u 边颜色一定和 v-w 相同，同理 x-v 边的颜色一定和 u-w 相同；此时 x 不能向环外第二个点连边，n=4 可以爆搜解决（同理可以爆搜 n 更小的情况，方便之后的处理）。如果 u 连向了 x，v 连向了 y；则由于 x-u-v-y 和 x-u-w-v-y 可得 x-u,v-y 选择任意一种颜色都会不合法。

      2. 否则环上只有一个点 u 能和环外连边，此时环外面的边只能都和 v-w 边同色。枚举 v-w 边以找出所有这样的环的数量 c 之后，其对方案数的贡献为 6c。

  2. 考虑某个环有两种颜色的情况（此时环上有三种颜色的方案可以直接视为非法）。此时一定存在第三种颜色的边 u-v，令 u 可以不通过 u-v 连向环上的某个点 w，w 在环上相邻的点为 x,y；则 w-x,w-y 中一定有一种颜色在环上出现了两次，去掉一条出现了两次的颜色的边之后一定会形成一条有三种颜色的路径。

综上，每个环只能有一种颜色，从而每个点双内部的边只能有一种颜色。考虑建出圆方树，则所有方点一定需要凑齐三种颜色，则一定存在某个圆点满足每个儿子的子树内的方点只有一种颜色，计算每个圆点的出边数量即可。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=200010;
const int md=998244353;
int n,m,i,j,u,v,w,a,t=1,tim,top;
int h[maxn],f[maxn],d[maxn],T[3];
int dfn[maxn],low[maxn],stk[maxn];
int p2[maxn],p3[maxn]; bool vis[maxn];
struct edge{int to,nxt;}E[maxn<<1];
bool dfs(int p){
    vis[p]=1; int lp,to;
    for(lp=h[p];lp;lp=E[lp].nxt){
        if(vis[to=E[lp].to]) continue;
        w+=(!(T[f[lp>>1]]++));
        if(w==3||dfs(to)) return 1;
        w-=(!(--T[f[lp>>1]]));
    }
    return vis[p]=0;
}
void color(int p){
    if(p>m){
        for(i=1,w=0;i<=n;++i){
            if(dfs(i)){
                memset(T,0,12);
                memset(vis+1,0,n);
                ++a; break;
            }
        }
        return;
    }
    f[p]=0; color(p+1);
    f[p]=1; color(p+1);
    f[p]=2; color(p+1);
}
inline void Add(int &x,int y){x-=((x+=y)>=md)*md;}
void tarjan(int p){
    dfn[p]=low[p]=++tim;
    stk[++top]=p; int lp,to;
    for(lp=h[p];lp;lp=E[lp].nxt){
        to=E[lp].to;
        if(!dfn[to]){
            tarjan(to);
            if(low[to]==dfn[p]){
                for(u=0;u!=p;++f[u=stk[top--]]);
                stk[++top]=p;
            }
            else low[p]=min(low[p],low[to]);
        }
        else low[p]=min(low[p],dfn[to]);
    }
}
int main(){
    p2[0]=p3[0]=1;
    for(i=1;i<maxn;++i){
        Add(p2[i]=p2[i-1],p2[i-1]);
        p3[i]=(3LL*p3[i-1])%md;
    }
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;++i){
        scanf("%d%d",&u,&v); 
        ++d[u]; ++d[v];
        E[++t]={v,h[u]}; h[u]=t;
        E[++t]={u,h[v]}; h[v]=t;
    }
    if(n<=4){
        color(1);
        printf("%d\n",a);
        return 0;
    }
    a=((p3[m]+3-3LL*p2[m])%md+md)%md;
    for(i=2;i<=t;i+=2){
        u=E[i].to; v=E[i|1].to;
        if(d[u]==2&&d[v]==2){
            if(E[j=h[u]].to==v) j=E[j].nxt; w=E[j].to; 
            if(E[j=h[v]].to==u) j=E[j].nxt; if(w==E[j].to) Add(a,md-6);
        }
    } 
    tarjan(1);
    for(i=1;i<=n;++i)
        Add(a,((3LL*p2[f[i]]-p3[f[i]]-3)%md+md)%md);
    printf("%d\n",a);
    return 0;
}