虚树+树形DP--luoguP4426 [HNOI/AHOI2018]毒瘤

本文主要是介绍虚树+树形DP--luoguP4426 [HNOI/AHOI2018]毒瘤，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

虚树毒瘤题

首先注意到 $m$ 只比 $n$ 大 $10$ ，所以可以随便找个生成树，把 $m$ 多出来的边上的点都拎出来建一个虚树，可以枚举每条边的深度较浅的那个点选不选，在虚树上树形 $d p$ ，然后发现虚树上父亲到儿子的系数是不变的，所以可以树形 $d p$ 预处理出来

$k [u] [0 / 1] [0 / 1]$ 表示 $u$ 到 $fa_u$ 中 $fa_u$ 选或不选， $u$ 选或不选的系数，然后每次枚举之后再虚树上预处理就好

细节非常多

代码如下：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#define N 100005
#define LL long long
using namespace std;
const int mod=998244353;template<class T>inline void rd(T &x){x=0; short f=1; char c=getchar();while(c<'0' || c>'9') f=c=='-'?-1:1,c=getchar();while(c<='9' && c>='0') x=x*10+c-'0',c=getchar();x*=f;
}int n,m,cnt,head[N],nxt[N<<1],to[N<<1],ecnt,dep[N],f[N][20];
int stk[N],top,dfn[N],siz[N],fat[N],a[N],tot,num;
int ed,dp[N][2],k[N][2][2],cho[N],g[N][2],ans;
bool vis[N];
vector<int> vec[N];struct EDGE{int fr,to;}edge[15];inline int find(int x){return x==fat[x]?x:(fat[x]=find(fat[x]));}
inline bool cmp(int x,int y){return dfn[x]<dfn[y];}inline void add(int x,int y){to[++cnt]=y,nxt[cnt]=head[x],head[x]=cnt;to[++cnt]=x,nxt[cnt]=head[y],head[y]=cnt;
}
inline void add1(int x,int y){vec[x].push_back(y);}void dfs(int u,int fa){siz[u]=1; dfn[u]=++num;for(int i=head[u],v;i;i=nxt[i])if((v=to[i])!=fa){dep[v]=dep[u]+1; f[v][0]=u;for(int j=1;j<=17;j++)f[v][j]=f[f[v][j-1]][j-1];dfs(v,u);siz[u]+=siz[v];}
}inline int LCA(int x,int y){if(dep[x]<dep[y]) swap(x,y);for(int i=17;i>=0;i--)if(dep[f[x][i]]>=dep[y]) x=f[x][i];if(x==y) return x;for(int i=17;i>=0;i--)if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];return f[x][0];
}void DP_tot(int u,int ban){dp[u][0]=dp[u][1]=1;for(int i=head[u],v;i;i=nxt[i])if((v=to[i])!=f[u][0] && v!=ban && !vis[v]){DP_tot(v,ban);dp[u][0]=1LL*dp[u][0]*((dp[v][0]+dp[v][1])%mod)%mod;dp[u][1]=1LL*dp[u][1]*dp[v][0]%mod;}
}inline void work(int x,int y){k[y][0][0]=1,k[y][1][1]=1;for(int i=y;f[i][0]!=x;i=f[i][0]){DP_tot(f[i][0],i); vis[f[i][0]]=1;int tmp0=k[y][0][0],tmp1=k[y][0][1];k[y][0][0]=1LL*dp[f[i][0]][0]*(k[y][0][0]+k[y][1][0])%mod;k[y][0][1]=1LL*dp[f[i][0]][0]*(k[y][0][1]+k[y][1][1])%mod;k[y][1][0]=1LL*dp[f[i][0]][1]*tmp0%mod;k[y][1][1]=1LL*dp[f[i][0]][1]*tmp1%mod;}
}inline void build(){int x,y,z;sort(a+1,a+tot+1,cmp);num=tot; ed=1<<ecnt;for(int i=2;i<=num;i++){x=a[i-1],y=a[i];z=LCA(x,y);if(!vis[z]) a[++tot]=z,vis[z]=1;}if(!vis[1]) a[++tot]=1,vis[1]=1;sort(a+1,a+tot+1,cmp); stk[++top]=a[1];for(int i=2;i<=tot;i++){while(top && dfn[stk[top]]+siz[stk[top]]<=dfn[a[i]]) top--;add1(stk[top],a[i]); stk[++top]=a[i];}
}void dfs_pre(int u){for(int i=0;i<vec[u].size();i++){dfs_pre(vec[u][i]);work(u,vec[u][i]);}dp[u][0]=dp[u][1]=1;for(int i=head[u],v;i;i=nxt[i])if((v=to[i])!=f[u][0] && !vis[v]){DP_tot(v,0);dp[u][0]=1LL*dp[u][0]*((dp[v][0]+dp[v][1])%mod)%mod;dp[u][1]=1LL*dp[u][1]*dp[v][0]%mod;}
}void DP(int u){g[u][1]=dp[u][1],g[u][0]=dp[u][0];for(int i=0,v;i<vec[u].size();i++){v=vec[u][i];DP(v);int k0=(1LL*k[v][0][0]*g[v][0]%mod+1LL*k[v][0][1]*g[v][1]%mod)%mod;int k1=(1LL*k[v][1][0]*g[v][0]%mod+1LL*k[v][1][1]*g[v][1]%mod)%mod;g[u][0]=1LL*g[u][0]*((k0+k1)%mod)%mod;g[u][1]=1LL*g[u][1]*k0%mod;}if(~cho[u]) g[u][cho[u]^1]=0;
}inline void solve(){for(int j=1;j<=ecnt;j++) if(dfn[edge[j].fr]>dfn[edge[j].to]) swap(edge[j].fr,edge[j].to);for(int i=0;i<ed;i++){memset(cho,-1,sizeof cho);bool flg=true;for(int j=1;j<=ecnt;j++)if((1<<(j-1))&i){if(cho[edge[j].fr]==0 || cho[edge[j].to]==1) {flg=false;break;}cho[edge[j].fr]=1,cho[edge[j].to]=0;}else{if(cho[edge[j].fr]==1) {flg=false;break;}cho[edge[j].fr]=0;}if(!flg) continue; DP(1);(ans+=(g[1][0]+g[1][1])%mod)%=mod;}
}int main(){//freopen("in.in","r",stdin);//freopen("out.out","w",stdout);rd(n),rd(m); int x,y;for(int i=1;i<=n;i++) fat[i]=i;for(int i=1;i<=m;i++){rd(x),rd(y);int fx=find(x),fy=find(y);if(fx!=fy) fat[fx]=fy,add(x,y);else {edge[++ecnt].fr=x,edge[ecnt].to=y;if(!vis[x]) a[++tot]=x,vis[x]=1;if(!vis[y]) a[++tot]=y,vis[y]=1;}}dep[1]=1; dfs(1,0); build(); dfs_pre(1); solve();printf("%d\n",ans);return 0;
}