从前有一名毒瘤。
毒瘤最近发现了量产毒瘤题的奥秘。考虑如下类型的数据结构题：给出一个数组，要求支持若干种奇奇怪怪的修改操作（比如区间加一个数，或者区间开平方），并支持询问区间和。毒瘤考虑了n个这样的修改操作，并编号为\(1\sim n\)。当毒瘤要出数据结构题的时候，他就将这些修改操作中选若干个出来，然后出成一道题。
当然了，这样出的题有可能不可做。通过精妙的数学推理，毒瘤揭露了这些修改操作的关系：有m对“互相排斥”的修改操作，第i对是第ui个操作和第vi个操作。当一道题同时含有ui和vi这两个操作时，这道题就会变得不可做。另一方面，一道题中不包含任何“互相排斥”的修改操作时，这个题就是可做的。此外，毒瘤还发现了一个规律：m-n是一个很小的数字，且任意两个修改操作都是连通的。两个修改操作a,b是连通的，当且仅当存在若干操作\(t_0,t_1,...,t_l\)，使得\(t_0=a,t_l=b\)，且对1≤i≤l，\(t_{i-1}\)和\(t_i\)都是“互相排斥”的修改操作。
一堆“互相排斥”的修改操作称为互斥对。现在毒瘤想知道，给定值n和m个互斥对，他共能出出多少道可做的不同的数据结构题。两道数据结构题是不同的，当且仅当有一个修改操作在其中一道题中存在，而在另一道题中不存在。
输入格式：
第一行为正整数n,m。
接下来m行，每行两个正整数u,v，代表一对“互相排斥”的修改操作。
输出格式：
输出一行一个整数，代表毒瘤可以出的可做的不同的“互相排斥”的修改操作的个数。这个数可能很大，所以只输出模998244353后的值。
虚树。
先处理出一颗生成树，考虑到非树边很少，考虑暴力枚举非树边两端的状态，复杂度\(O(4^{n-m+1}n)\)。
然后优化一下，对于一条非树边，两端的状态只需要枚举\((1,0)\)和\((0,1)\)就好了，\((1,1)\)显然不合法，\((0,0)\)可以在\(dp\)的时候得到。复杂度\(O(2^{n-m+1}n)\)。
考虑到上面的过程枚举时，树边是不变的，也就是说，可以考虑把非树边所在的点建出一颗虚树，然后对于虚树上的点，\(dp\)方程一定可以表示成：\[ f_{u,0/1}=\prod_{v\in son_u}k_{0/1,0}f_{v,0}+k_{0/1,1}f_{v,1} \] 其中\(k\)为固定的系数，对于虚树上每条边，这个转移都是固定的。
所以可以\(O(n)\)先在原树\(dp\)出系数，然后暴力枚举关键点状态暴力虚树上\(dp\)就好了。
复杂度\(O(n+2^{2(m-n+1)}(n-m+1))\)，足以通过此题。
#include<bits/stdc++.h> using namespace std; #define int long long void read(int &x) { x=0;int f=1;char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f; for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f; } void print(int x) { if(x<0) putchar('-'),x=-x; if(!x) return ;print(x/10),putchar(x+48); } void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');} const int mod = 998244353; const int maxn = 3e5+10; int n,m,s[100],tt[100],cnt,sz[maxn],dfn[maxn],dep[maxn],use[maxn],val[maxn],vis[maxn],g[maxn][2],pr[maxn]; struct data {int k[2][2];}epsilon; struct Dsu { int fa[maxn]; void init() {for(int i=1;i<=n;i++) fa[i]=i;} int find(int x) {return fa[x]==x?x:fa[x]=find(fa[x]);} }dsu; struct Input_Tree { int head[maxn],tot,f[maxn][20],dfn_cnt; struct edge{int to,nxt;}e[maxn<<1]; void add(int u,int v) {e[++tot]=(edge){v,head[u]},head[u]=tot;} void ins(int u,int v) {add(u,v),add(v,u);} void dfs(int x,int fa) { sz[x]=1,dfn[x]=++dfn_cnt,dep[x]=dep[fa]+1,f[x][0]=fa; for(int i=1;i<=19;i++) f[x][i]=f[f[x][i-1]][i-1]; for(int i=head[x];i;i=e[i].nxt) if(e[i].to!=fa) dfs(e[i].to,x),sz[x]+=sz[e[i].to]; } int lca(int x,int y) { if(dep[x]<dep[y]) swap(x,y); for(int i=19;~i;i--) if(dep[f[x][i]]>=dep[y]) x=f[x][i]; if(x==y) return x; for(int i=19;~i;i--) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i]; return f[x][0]; } void dp(int x,int fa) { int bo=1;g[x][0]=g[x][1]=1; for(int i=head[x];i;i=e[i].nxt) if(e[i].to!=fa) { bo=0,dp(e[i].to,x);int v=e[i].to; g[x][0]=1ll*g[x][0]*(g[v][0]+g[v][1])%mod; g[x][1]=1ll*g[x][1]*g[v][0]%mod; } if(bo) g[x][0]=g[x][1]=1; } int ns[maxn][2],nt[maxn][2]; data get(int x,int fa) { ns[x][0]=1,ns[x][1]=0; nt[x][0]=0,nt[x][1]=1; while(x!=fa) { pr[x]=1; int pre=x;x=f[x][0];ns[x][0]=ns[x][1]=nt[x][0]=nt[x][1]=1; ns[x][0]=1ll*ns[x][0]*(ns[pre][0]+ns[pre][1])%mod; ns[x][1]=1ll*ns[x][1]*ns[pre][0]%mod; nt[x][0]=1ll*nt[x][0]*(nt[pre][0]+nt[pre][1])%mod; nt[x][1]=1ll*nt[x][1]*nt[pre][0]%mod; if(x==fa) break; for(int i=head[x];i;i=e[i].nxt) if(e[i].to!=f[x][0]&&e[i].to!=pre) { int v=e[i].to; ns[x][0]=1ll*ns[x][0]*(g[v][0]+g[v][1])%mod; ns[x][1]=1ll*ns[x][1]*g[v][0]%mod; nt[x][0]=1ll*nt[x][0]*(g[v][0]+g[v][1])%mod; nt[x][1]=1ll*nt[x][1]*g[v][0]%mod; } } data ans;pr[fa]=1; ans.k[0][0]=ns[x][0],ans.k[1][0]=ns[x][1]; ans.k[0][1]=nt[x][0],ans.k[1][1]=nt[x][1]; return ans; } }T; int cmp(int x,int y) {return dfn[x]<dfn[y];} struct Virtual_Tree { int head[maxn],tot; struct edge{int to,nxt;data k;}e[maxn<<1]; void add(int u,int v) {e[++tot]=(edge){v,head[u],epsilon},head[u]=tot;} void ins(int u,int v) {add(u,v),add(v,u);} int in[maxn],k,use[maxn],used,sta[maxn],top,ban[maxn],f[maxn][2],val[maxn][2]; void build() { sort(in+1,in+k+1,cmp);k=unique(in+1,in+k+1)-in-1; sta[++top]=1; for(int i=1;i<=k;i++) { if(in[i]==1) continue; int t=T.lca(in[i],sta[top]),pre=-1; while(dfn[sta[top]]>dfn[t]&&dfn[sta[top]]<dfn[t]+sz[t]) { if(pre!=-1) ins(sta[top],pre); pre=sta[top],top--; } if(pre!=-1) ins(t,pre); if(sta[top]!=t) sta[++top]=t; sta[++top]=in[i]; } int pre=-1; while(top) { if(pre!=-1) ins(sta[top],pre); pre=sta[top],top--; } } void dfs(int x,int fa) { use[x]=1; for(int i=head[x];i;i=e[i].nxt) if(e[i].to!=fa) dfs(e[i].to,x); } void make(int x,int fa) { for(int i=head[x];i;i=e[i].nxt) if(e[i].to!=fa) { e[i].k=T.get(e[i].to,x); make(e[i].to,x); } } void dp(int x,int fa) { f[x][0]=val[x][0],f[x][1]=val[x][1]; for(int i=head[x];i;i=e[i].nxt) if(e[i].to!=fa) { dp(e[i].to,x);data u=e[i].k;int v=e[i].to; f[x][0]=1ll*f[x][0]*(f[v][0]*u.k[0][0]%mod+f[v][1]*u.k[0][1]%mod)%mod; f[x][1]=1ll*f[x][1]*(f[v][0]*u.k[1][0]%mod+f[v][1]*u.k[1][1]%mod)%mod; } if(ban[x]==0) f[x][1]=0; else if(ban[x]==1) f[x][0]=0; } void get_val(int x,int fa) { val[x][0]=val[x][1]=1; for(int i=T.head[x],v=T.e[i].to;i;i=T.e[i].nxt,v=T.e[i].to) if(!pr[v]) { val[x][0]=1ll*val[x][0]*(g[v][0]+g[v][1])%mod; val[x][1]=1ll*val[x][1]*g[v][0]%mod; } for(int i=head[x];i;i=e[i].nxt) if(e[i].to!=fa) get_val(e[i].to,x); } void solve() for(int i=1;i<=cnt;i++) in[++k]=s[i],in[++k]=tt[i],vis[s[i]]=1,vis[tt[i]]=1; build();make(1,0);int ans=0; memset(ban,-1,sizeof ban); get_val(1,0); for(int st=0;st<(1<<k);st++) { for(int i=1;i<=k;i++) if(st&(1<<(i-1))) ban[in[i]]=1; else ban[in[i]]=0; for(int i=1;i<=cnt;i++) if(ban[s[i]]==1&&ban[tt[i]]==1) goto loop; dp(1,0); ans=(0ll+ans+f[1][0]+f[1][1])%mod; loop:; } write(ans); } }VT; signed main() { read(n),read(m);dsu.init(); for(int i=1,x,y;i<=m;i++) { read(x),read(y);int u=dsu.find(x),v=dsu.find(y); if(u==v) s[++cnt]=x,tt[cnt]=y; else dsu.fa[u]=v,T.ins(x,y); } T.dfs(1,0),T.dp(1,0);VT.solve(); return 0; }转载于:https://www.cnblogs.com/hbyer/p/10243535.html
