前言
話說在\(Loj\)下了個資料發現這題的名字叫\(fgo\)
正題
題目連結:https://www.luogu.com.cn/problem/P5405
題目大意
\(n\)張卡的權值為\(1/2/3\)的機率權重分别是\(p_{x,1/2/3}\)，然後按照權值每次獲得一張未獲得的卡，然後再該出一棵有向樹（方向可以都是外向或内向的），求所有每條邊\((u,v)\)，\(u\)都比\(v\)先獲得的機率。
\(1\leq n\leq 1000,0\leq p_{i,j}\leq 10^6\)
解題思路
隻考慮外向樹的話就是水題了，因為顯然的\(x\)要排在子樹最前面的機率就是\(\frac{w_x}{\sum_{y\in subtree_x}w_y}\)。
然後直接\(n^2\)的\(dp\)就可以力。
但是現在有内向邊怎麼辦，還是考慮轉換成隻有外向的，也就是去掉一種限制。
去掉一種限制的話容斥是一個不錯的辦法，考慮的話就是恰好若幹條指定邊（内向邊），我們可以指定至少\(k\)跳内向邊不滿足條件，這樣就組成了一個外向森林，可以很容易處理出答案，而且這樣的容斥系數就是\((-1)^k\)。
然後直接\(dp\)就得了，設\(f_{i,j}\)表示到節點\(i\)然後權值和是\(j\)，如果限制一條内向邊就直接乘上一個\(-1\)就好了。
額這種樹形\(dp\)枚舉子樹大小可以做到\(n^2\)這個是老生常談了
時間複雜度\(O(n^2)\)
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const ll N=1100,P=998244353;
struct node{
ll to,next,w;
}a[N<<1];
ll n,tot,ans,ls[N],siz[N],w[N][3],f[N][3*N],g[N*3];
ll power(ll x,ll b){
ll ans=1;
while(b){
if(b&1)ans=ans*x%P;
x=x*x%P;b>>=1;
}
return ans;
}
void addl(ll x,ll y,ll w){
a[++tot].to=y;
a[tot].next=ls[x];
a[tot].w=w;
ls[x]=tot;return;
}
void dp(ll x,ll fa){
ll d=power(w[x][0]+w[x][1]+w[x][2],P-2);
siz[x]=3;
f[x][1]=w[x][0]*d%P;
f[x][2]=w[x][1]*d*2ll%P;
f[x][3]=w[x][2]*d*3ll%P;
for(ll e=ls[x];e;e=a[e].next){
ll y=a[e].to;
if(y==fa)continue;
dp(y,x);
if(a[e].w){
for(ll i=1;i<=siz[x];i++)
for(ll j=1;j<=siz[y];j++)
(g[i+j]-=f[x][i]*f[y][j]%P)%=P,(g[i]+=f[x][i]*f[y][j]%P)%=P;
}
else{
for(ll i=1;i<=siz[x];i++)
for(ll j=1;j<=siz[y];j++)
(g[i+j]+=f[x][i]*f[y][j]%P)%=P;
}
siz[x]+=siz[y];
for(ll i=1;i<=siz[x];i++)
f[x][i]=g[i],g[i]=0;
}
for(int i=1;i<=siz[x];i++)
f[x][i]=f[x][i]*power(i,P-2)%P;
return;
}
signed main()
{
scanf("%lld",&n);
for(ll i=1;i<=n;i++)
scanf("%lld%lld%lld",&w[i][0],&w[i][1],&w[i][2]);
for(ll i=1;i<n;i++){
ll x,y;scanf("%lld%lld",&x,&y);
addl(x,y,0);addl(y,x,1);
}
dp(1,0);
for(ll i=1;i<=siz[1];i++)
(ans+=f[1][i])%=P;
printf("%lld\n",(ans+P)%P);
return 0;
}