题解 洛谷 P5405 【[CTS2019]氪金手游】

先考虑外向树的情况,那么对于每个节点,该节点都是其子树内第一个抽到的。假设 (W) 都已确定,(sum) 为所有 (W) 的和,(s_x)(x) 子树内 (W) 的和,得最终答案为:

[ prod_{x=1}^n frac{W_x}{sum} sum_{i=0}^infty (frac{sum-s_x}{sum})^i ]

这个式子是在考虑 (x) 什么时候被抽到,这里抽到其子树外的点是合法的,并不影响 (x),经过化简后得:

[ prod_{x=1}^n frac{W_x}{s_x} ]

因为 (W) 不确定,所以通过树形 (DP) 来解决,设 (f_{x,i}) 表示考虑节点 (x),其子树 (W) 的和为 (i) 的合法概率,通过合并子树来转移即可。

考虑加上反向边,正难则反,用容斥来解决。反向边的贡献为不考虑这条边的限制条件,正向反向都可以的贡献减去该边为正向边的贡献。

不考虑限制条件可以看作将该边删去,树形 (DP) 时注意枚举范围为子树大小,来保证复杂度为 (O(n^2))

(code:)

#include<bits/stdc++.h>
#define maxn 3010
#define p 998244353
using namespace std;
typedef long long ll;
template<typename T> inline void read(T &x)
{
    x=0;char c=getchar();bool flag=false;
    while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    if(flag)x=-x;
}
ll n,ans;
ll f[maxn][maxn],g[maxn],siz[maxn];
struct edge
{
    int to,nxt;
}e[maxn];
int head[maxn],edge_cnt;
void add(int from,int to)
{
    e[++edge_cnt]=(edge){to,head[from]};
    head[from]=edge_cnt;
}
ll inv(ll x)
{
    ll v=1,y=p-2;
    while(y)
    {
        if(y&1) v=v*x%p;
        x=x*x%p,y>>=1;
    }
    return v;
}
void dfs(int x,int fa)
{
    siz[x]=1;
    for(int i=head[x];i;i=e[i].nxt)
    {
        int y=e[i].to;
        if(y==fa) continue;
        dfs(y,x);
        for(int j=1;j<=siz[x]*3;++j)
        {
            for(int k=1;k<=siz[y]*3;++k)
            {
                ll val=f[x][j]*f[y][k]%p;
                if(i&1) g[j+k]=(g[j+k]+val)%p;
                else g[j]=(g[j]+val)%p,g[j+k]=(g[j+k]-val+p)%p;
            }
        }
        siz[x]+=siz[y];
        for(int j=1;j<=siz[x]*3;++j) f[x][j]=g[j],g[j]=0;
    }
    for(int i=1;i<=siz[x]*3;++i) f[x][i]=f[x][i]*inv(i)%p;
}
int main()
{
    read(n);
    for(int i=1;i<=n;++i)
    {
        ll a1,a2,a3,t;
        read(a1),read(a2),read(a3),t=inv(a1+a2+a3);
        f[i][1]=1*a1*t%p,f[i][2]=2*a2*t%p,f[i][3]=3*a3*t%p;
    }
    for(int i=1;i<n;++i)
    {
        int x,y;
        read(x),read(y);
        add(x,y),add(y,x);
    }
    dfs(1,0);
    for(int i=1;i<=n*3;++i) ans=(ans+f[1][i])%p;
    printf("%lld",ans);
    return 0;
}
原文地址:https://www.cnblogs.com/lhm-/p/13388981.html