Description
Solution
首先它的限制关系是一个树形图
首先考虑如果它是一个外向树该怎么做。这是很简单的,我们相当于每个子树的根都是子树中最早出现的点,概率是容易计算的。
设DP状态\(f[i][j]\)为做到以i为根的子树,子树中权值W的和为j且满足限制关系的概率。 然后就可以直接利用子树背包DP来转移了。如果有些边是反向(儿子到父亲)的,我们可以通过容斥来把这些边反过来,要么是彻底没有这条边的限制,要么是反向变成父亲到儿子方向,系数乘一个(-1)即可。
具体可以参考代码。Code
#include#define fo(i,a,b) for(int i=a;i<=b;++i)#define fod(i,a,b) for(int i=a;i>=b;--i)#define N 1005#define LL long long#define mo 998244353using namespace std;int n,fs[N],nt[2*N],dt[2*N],sz[N],m1;LL ny[N],ap[N][4],f[N][3*N],pr[2*N],g[3*N],np[3*N];LL ksm(LL k,LL n){ LL s=1; for(;n;n>>=1,k=k*k%mo) if(n&1) s=s*k%mo; return s;}void link(int x,int y){ nt[++m1]=fs[x]; dt[fs[x]=m1]=y;}void dfs(int k,int fa){ f[k][0]=1; for(int i=fs[k];i;i=nt[i]) { int p=dt[i]; if(p!=fa) { dfs(p,k); fo(x,0,3*sz[k]) fo(y,1,3*sz[p]) { (g[x+y]+=f[k][x]*f[p][y]%mo*pr[i]%mo)%=mo; if(pr[i]==mo-1) (g[x]+=f[k][x]*f[p][y]%mo)%=mo; } sz[k]+=sz[p]; fo(j,0,3*sz[k]) f[k][j]=g[j],g[j]=0; } } sz[k]++; fod(i,3*sz[k],0) { f[k][i]=0; fo(j,1,3) if(i>=j) (f[k][i]+=f[k][i-j]*ny[k]%mo*ap[k][j]%mo*np[i]%mo*(LL)j%mo)%=mo; }}int main(){ cin>>n; fo(i,1,n) { fo(j,1,3) scanf("%d",&ap[i][j]),ny[i]+=ap[i][j]; ny[i]=ksm(ny[i]%mo,mo-2); } fo(i,1,3*n) np[i]=ksm(i,mo-2); fo(i,1,n-1) { int x,y; scanf("%d%d",&x,&y); link(x,y),link(y,x); pr[m1-1]=1,pr[m1]=mo-1; } dfs(1,0); LL ans=0; fo(i,1,3*n) (ans+=f[1][i])%=mo; printf("%lld\n",ans);}