CTS2019 氪金手游

link

如果所有边都指向根的方向，那么就是要求每个点在子树中所有点之前，

所以考虑子树的$w_i$和 和$w_x$（$x$是子树根），那么概率就是$\frac{w_x}{\sum w_i}$

当然$w_i$也包含$w_x$

这东西可以DP f[x][y]表示以$x$为根，子树$w_i$和为$y$ 满足条件的概率。

如果有反向边，那么容斥是否不满足，如果不满足则为正向边，否则就不管这条边（对子树大小的贡献）

容易看出有$k$条反边不满足的贡献是$(-1)^k$，所以就可以直接类似的DP了

code version1:

const int p=998244353;
int a[1005][4];
int fpm(int a,int b){
    int c=1;
    for(;b;b>>=1,a=a*a%p)if(b&1)c=c*a%p;
    return c;
}
int inv[3005];
vector<pii> to[1005];
int f[1005][3005],siz[3005];
int g[3005],h[3005];
int cnt[1005];
void dfs(int x,int fa){
    for(auto i:to[x])if(i.x!=fa){
        dfs(i.x,x);
    }
    for(int j=1;j<=3;++j){
        int s=0;
        g[0]=1;
        for(auto i:to[x])if(i.x!=fa){
            for(int x=0;x<=s;++x){
                if(i.y)h[x]=(h[x]+g[x]*cnt[i.x])%p;
                for(int y=0;y<=siz[i.x];++y)
                    if(i.y)
                        h[x+y]=(h[x+y]-g[x]*f[i.x][y]%p+p)%p;
                    else
                        h[x+y]=(h[x+y]+g[x]*f[i.x][y]%p)%p;
            }
            for(int x=0;x<=s+siz[i.x];++x){g[x]=h[x];h[x]=0;}
            s+=siz[i.x];
        }
        for(int i=0;i<=s;++i)f[x][i+j]=(f[x][i+j]+g[i]*a[x][j]%p*j*inv[i+j])%p;
        chkmax(siz[x],s+j);
    }
    for(int i=0;i<=siz[x];++i)cnt[x]=(cnt[x]+f[x][i])%p;
}
signed main(){
#ifdef QAQAutoMaton
    freopen("fgo.in","r",stdin);
    freopen("fgo.out","w",stdout);
#endif
    int n;
    read(n);
    inv[1]=1;
    for(int i=2;i<=n*3;++i){
        inv[i]=(p-p/i)*inv[p%i]%p;
    }
    for(int i=1;i<=n;++i){
        read(a[i][1]);
        read(a[i][2]);
        read(a[i][3]);
        int w=fpm(a[i][1]+a[i][2]+a[i][3],p-2)%p;    
        a[i][1]=a[i][1]*w%p;
        a[i][2]=a[i][2]*w%p;
        a[i][3]=a[i][3]*w%p;
    }
    int u,v;
    for(int i=1;i<n;++i){
        read(u,v);
        to[u].push_back(make_pair(v,0));
        to[v].push_back(make_pair(u,1));
    }
    dfs(1,0);
    int ans=0;
    for(int i=0;i<=n*3;++i)ans=(ans+f[1][i])%p;
    write(ans,'\n');
    return 0;
}

code version2:

const int p=998244353;
int a[1005][4];
int fpm(int a,int b){
    int c=1;
    for(;b;b>>=1,a=a*a%p)if(b&1)c=c*a%p;
    return c;
}
int inv[3005];
vector<pii> to[1005];
int f[1005][3005],siz[3005];
int g[3005],h[3005];
int cnt[1005];
void dfs(int x,int fa){
    for(auto i:to[x])if(i.x!=fa)dfs(i.x,x);
    int s=3;
    g[0]=0;
    g[1]=a[x][1];
    g[2]=a[x][2]*2%p;
    g[3]=a[x][3]*3%p;
    for(auto i:to[x])if(i.x!=fa){
        for(int x=0;x<=s;++x){
            if(i.y)h[x]=(h[x]+g[x]*cnt[i.x])%p;
            for(int y=0;y<=siz[i.x];++y)
                if(i.y)
                    h[x+y]=(h[x+y]-g[x]*f[i.x][y]%p+p)%p;
                else
                    h[x+y]=(h[x+y]+g[x]*f[i.x][y]%p)%p;
        }
        for(int x=0;x<=s+siz[i.x];++x){g[x]=h[x];h[x]=0;}
        s+=siz[i.x];
    }
    for(int i=0;i<=s;++i)f[x][i]=g[i]*inv[i]%p;
    siz[x]=s;
    for(int i=0;i<=siz[x];++i)cnt[x]=(cnt[x]+f[x][i])%p;
}
signed main(){
#ifdef QAQAutoMaton
    freopen("fgo.in","r",stdin);
    freopen("fgo.out","w",stdout);
#endif
    int n;
    read(n);
    inv[1]=1;
    for(int i=2;i<=n*3;++i){
        inv[i]=(p-p/i)*inv[p%i]%p;
    }
    for(int i=1;i<=n;++i){
        read(a[i][1]);
        read(a[i][2]);
        read(a[i][3]);
        int w=fpm(a[i][1]+a[i][2]+a[i][3],p-2)%p;    
        a[i][1]=a[i][1]*w%p;
        a[i][2]=a[i][2]*w%p;
        a[i][3]=a[i][3]*w%p;
    }
    int u,v;
    for(int i=1;i<n;++i){
        read(u,v);
        to[u].push_back(make_pair(v,0));
        to[v].push_back(make_pair(u,1));
    }
    dfs(1,0);
    int ans=0;
    for(int i=0;i<=n*3;++i)ans=(ans+f[1][i])%p;
    write(ans,'\n');
    return 0;
}