解析
顾名思义,十分毒瘤
但有一说一,相对来说这题没有之前做的那两个黑题那么(重读)恶心
而且本题如果放在考场上,暴力枚举非树边的状态dp就可以拿到70分的好成绩(改一改能改到75)
现在考虑正解
注意到,每次暴力枚举非树边的状态进行dp时,状态发生改变的其实来来回回就是少数的几个点而已
所以想到虚树
首先把非树边的端点作为特殊点建出虚树
如何转移呢?
考虑到,两个关键点u,v之间的“连边”是一条有分支的链
不能直接按定义正常转移
但是我们发现,只要这个链的形态不变,
d
p
v
dp_v
dpv转移到
d
p
u
dp_u
dpu的系数是不变的
因此,我们可以预先暴力求出这个系数,再进行转移
注意到,所有转移加起来最多把整颗树都搜一遍,复杂度是
O
(
n
)
O(n)
O(n)的
还要注意到,由于还有的点不在虚树上,所以关键点的dp初值不是1,还要单独求
这个比较好求,暴力往没有关键点的子树上搜索就行了
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
const int N=1e6+100;
const int mod=998244353;
inline ll read(){
ll x(0),f(1);char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
int n,m;
struct node{
int to,nxt;
ll k[2][2];
} p1[N<<1],p2[10050];
int fi1[N],cnt1,fi2[N],cnt2;
inline void addline(int x,int y){
p1[++cnt1]=(node){y,fi1[x]};
fi1[x]=cnt1;
return;
}
ll dp[N][2];
int op[N],fa[N];
bool jd[N],vis[N];
//op=1:must not be chosen
//op=2:must be chosen
struct edge{
int x,y;
} e[50];
int tot;
int pos[N],tim;
int pl[N][18],dep[N],siz[N];
void find(int x,int from){
vis[x]=1;
pos[x]=++tim;
for(int k=1;pl[x][k-1];k++) pl[x][k]=pl[pl[x][k-1]][k-1];
siz[x]=1;
for(int i=fi1[x]; ~i; i=p1[i].nxt) {
if(i==(from^1)) continue;
int to=p1[i].to;
if(vis[to]) {
if(!jd[i]) {
jd[i]=jd[i^1]=1;
e[++tot]=(edge){x,to};
}
}
else{
dep[to]=dep[x]+1;pl[to][0]=x;
fa[to]=x;
find(to,i);
siz[x]+=siz[to];
}
}
//printf("x=%d fa=%d\n",x,fa[x]);
return;
}
inline int Lca(int x,int y){
if(pos[x]<=pos[y]&&pos[y]<=pos[x]+siz[x]-1) return x;
for(int k=17;k>=0;k--){
int o=pl[x][k];
if(!o||(pos[o]<=pos[y]&&pos[y]<=pos[o]+siz[o]-1)) continue;
x=o;
}
return pl[x][0];
}
ll ans;
int tag[N],Top;
void init(int x,int goal,int op){
if(x==goal){
dp[x][op]=1;dp[x][!op]=0;return;
}
dp[x][0]=dp[x][1]=1;
for(int i=fi1[x];~i;i=p1[i].nxt){
int to=p1[i].to;
if(to==fa[x]||jd[i]) continue;
if(x==Top&&tag[to]!=tim) continue;
init(to,goal,op);
(dp[x][0]*=(dp[to][0]+dp[to][1]))%=mod;
(dp[x][1]*=dp[to][0])%=mod;
}
return;
}
void Tag(int x,int top){
if(fa[x]==top) tag[x]=tim;
else Tag(fa[x],top);
}
inline void Addline(int x,int y){
p2[++cnt2]=(node){y,fi2[x]};
//printf(" add:%d->%d\n",x,y);
fi2[x]=cnt2;++tim;Tag(y,x);Top=x;
init(x,y,0);p2[cnt2].k[0][0]=dp[x][0];p2[cnt2].k[0][1]=dp[x][1];
init(x,y,1);p2[cnt2].k[1][0]=dp[x][0];p2[cnt2].k[1][1]=dp[x][1];
//printf("%d->%d k[0][0]=%d k[0][1]=%d k[1][0]=%d k[1][1]=%d\n",x,y,p2[cnt2].k[0][0],p2[cnt2].k[0][1],p2[cnt2].k[1][0],p2[cnt2].k[1][1]);
return;
}
void pre(int x){
dp[x][0]=dp[x][1]=1;
for(int i=fi1[x];~i;i=p1[i].nxt){
int to=p1[i].to;
if(tag[to]||to==fa[x]||jd[i]) continue;
pre(to);
(dp[x][0]*=(dp[to][0]+dp[to][1]))%=mod;
(dp[x][1]*=dp[to][0])%=mod;
}
return;
}
bool col[N];
bool cmp(int x,int y){
return pos[x]<pos[y];
}
int v[N],zhan[N],top;
ll ori[N][2];
void dfs(int x,int f){
dp[x][0]=ori[x][0];dp[x][1]=ori[x][1];
for(int i=fi2[x]; ~i; i=p2[i].nxt) {
int to=p2[i].to;
if(to==f) continue;
dfs(to,x);
dp[x][0]=((dp[to][0]*p2[i].k[0][0]%mod+dp[to][1]*p2[i].k[1][0]%mod)%mod*dp[x][0])%mod;
dp[x][1]=((dp[to][0]*p2[i].k[0][1]%mod+dp[to][1]*p2[i].k[1][1]%mod)%mod*dp[x][1])%mod;
}
if(op[x]) {
if(op[x]==1) dp[x][1]=0;
else dp[x][0]=0;
}
//printf(" x=%d dp0=%lld dp1=%lld op=%d\n",x,dp[x][0],dp[x][1],op[x]);
return;
}
int num;
void solve(int k) {
if(k>num){
//for(int i=1;i<=n;i++){
//printf(" i=%d op=%d\n",i,op[i]);
//}
dfs(1,0);
ll res=dp[1][0]+dp[1][1];
ans+=res;
ans%=mod;
//printf("res=%lld\n\n",res);
return;
}
int a=op[e[k].x],b=op[e[k].y];
if(op[e[k].x]!=2){
op[e[k].x]=1;
//printf("(%d %d)\n",1,2);
solve(k+1);
op[e[k].x]=a;
}
if(op[e[k].x]!=1&&op[e[k].y]!=2){
op[e[k].x]=2;
op[e[k].y]=1;
//printf("(%d %d)\n",2,1);
solve(k+1);
op[e[k].x]=a;op[e[k].y]=b;
}
return;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
memset(fi1,-1,sizeof(fi1));cnt1=-1;
memset(fi2,-1,sizeof(fi2));cnt2=-1;
n=read();m=read();
for(int i=1;i<=m;i++){
int x=read(),y=read();
addline(x,y);
addline(y,x);
}
find(1,-2);
num=tot;tot=0;
for(int i=1;i<=num;i++){
int x=e[i].x,y=e[i].y;
if(!col[x]) v[++tot]=x,col[x]=1;
if(!col[y]) v[++tot]=y,col[y]=1;
}
if(!col[1]) v[++tot]=1;
sort(v+1,v+1+tot,cmp);
zhan[top=1]=v[1];
//for(int i=1;i<=tot;i++) printf("%d ",v[i]);putchar('\n');
for(int i=2;i<=tot;i++){
int x=v[i],lca=Lca(x,zhan[top]);
//printf("v[1]=%d x=%d lca=%d\n",v[1],x,lca);
while(top>1&&dep[lca]<=dep[zhan[top-1]]){
Addline(zhan[top-1],zhan[top]);top--;
}
if(lca!=zhan[top]){
Addline(lca,zhan[top]);zhan[top]=lca;
}
zhan[++top]=x;
//for(int i=1;i<=top;i++) printf("%d ",zhan[i]);putchar('\n');
}//printf("ok");
while(top>1){
Addline(zhan[top-1],zhan[top]);top--;
}
for(int i=1;i<=n;i++){
if(i!=1&&fi2[i]==-1&&!col[i]) continue;
int x=i;
pre(x);
ori[x][0]=dp[x][0];ori[x][1]=dp[x][1];
//printf("x=%d ori0=%lld ori1=%lld\n",x,ori[x][0],ori[x][1]);
}
solve(1);
printf("%lld\n",ans);
return 0;
}
/*
*/