nowcoder375C 小G砍树 换根DP

nowcoder375C 小G砍树 换根DP

我们令 $f[i]$ 表示以 $i$ 为根的删除方案数.   这里一定要注意一件事情：根据我们的定义，我们已经默认 $i$ 点为根的子树在删除时 $i$ 是最后删除的.    然后按照换根 DP 的套路转移就行，但是转移的时候组合数一定要注意.    #include #include #include #define N 100007 #define ll long long #define mod 998244353 #define setIO(s) freopen(s".in","r",stdin) using namespace std; int qpow(int x,int y) { int tmp=1; for(;y;y>>=1,x=(ll)x*x%mod) if(y&1) tmp=(ll)tmp*x%mod; return tmp; } int edges,n; int f[N],inv[N],fac[N],hd[N],to[N<<1],nex[N<<1],size[N],g[N]; void add(int u,int v) { nex[++edges]=hd[u],hd[u]=edges,to[edges]=v; } int C(int x,int y) { return (ll)fac[x]*inv[y]%mod*inv[x-y]%mod; } void dfs(int u,int ff) { size[u]=1,f[u]=1; for(int i=hd[u];i;i=nex[i]) { int v=to[i]; if(v==ff) continue; dfs(v,u); f[u]=(ll)f[u]%mod*f[v]%mod*C(size[u]+size[v]-1,size[v])%mod; size[u]+=size[v]; } } void dfs2(int u,int ff) { if(u==1) g[u]=f[u]; for(int i=hd[u];i;i=nex[i]) { int v=to[i]; if(v==ff) continue; int remain=(ll)g[u]*qpow(f[v],mod-2)%mod*qpow(C(n-1,size[v]),mod-2)%mod; g[v]=(ll)f[v]*remain%mod*C(n-1,n-size[v])%mod; dfs2(v,u); } } int main() { // setIO("input"); int i,j; scanf("%d",&n); for(i=1;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。