Cptraser/ 三月 9, 2019/ 2019.3/ 0 comments

题面传送门
假设我们推出固定根的DP式(tot为已经枚举的子树size和):

    \[f[x]=\prod_{j\in son_x}f[j] * {tot\choose size[j]}\]

这只要考虑两个子树的删除序列合并即可。{x+y\choose y}
再考虑从根推回所有节点,考虑一个fa和一个son,要从fa推回son,就只要考虑son为fa的父亲,已经做完了son的其他节点。那么:

    \[f[son]=f[x] * \frac{size[son]}{n-size[son]}\]

#include<bits/stdc++.h>
using namespace std;

long long N,x,y,f[200005],size[200005],Ans;
vector<long long>A[200005];
long long Fac[200005],Inv[200005];
const long long Mod=998244353;
#define C(x,y) ((x<y)?(0):(Fac[x]*Inv[y]%Mod*Inv[x-y]%Mod))
void dfs(long long x,long long fa){
    f[x]=1;
    for(long long i=0;i<A[x].size();i++)if(A[x][i]^fa){
        dfs(A[x][i],x);size[x]+=size[A[x][i]];
        f[x]=(long long)(f[x]*f[A[x][i]]%Mod*C(size[x],size[A[x][i]])%Mod);
    }size[x]++;
}

long long Ksm(long long x,long long y){
    long long res=1;for(;y;y>>=1,x=x*x%Mod)if(y&1)res=res*x%Mod;return res;
}

void dfs1(long long x,long long fa){
    for(long long i=0;i<A[x].size();i++)if(A[x][i]^fa){
        f[A[x][i]]=(long long)(f[x]*size[A[x][i]]%Mod*Ksm(N-size[A[x][i]],Mod-2)%Mod);
        dfs1(A[x][i],x);
    }
}

int main(){
    cin>>N;Fac[0]=Fac[1]=1;
    for(long long i=2;i<=N*2;i++)Fac[i]=Fac[i-1]*i%Mod; 
    for(long long i=0;i<=N*2;i++)Inv[i]=Ksm(Fac[i],Mod-2);
    for(long long i=1;i<N;i++){
        cin>>x>>y;
        A[x].push_back(y),A[y].push_back(x);
    }dfs(1,0),dfs1(1,0);
    for(long long i=1;i<=N;i++)Ans=(long long)(Ans+f[i])%Mod;
    printf("%d\n",Ans);
}
Share this Post

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
*
*