CTS2019 氪金手游

发表于 2019-09-11 分类于题解

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;
}