一道概率神題，考試時沒讀清題考完看了學長的玄學題解看了好幾個小時

首先f[i][j]表示在點 i 為根的子樹中,向下最長輕鏈長度小于等于 j 的概率。

首先遞歸下去并求出子樹大小，然后枚舉重兒子，枚舉該點最長輕鏈長度，再次枚舉兒子節點并逐個

假設當前枚舉的重兒子是to1，枚舉到兒子節點to2，x最長輕鏈長度為k，設gs為v（to2）之前考慮的兒子中最長輕鏈長度為k的概率如果v（to1）=v（to2）即v（to2）為重兒子，則設fs為以v（to2）為根的子樹最長輕鏈長度為k的概率:

h[k]=(fs*g[k]%mod+gs*f[to2][k]%mod-gs*fs+mod)%mod;

?

如果v（to2）是輕兒子，則設fs為以v（to2）為根的子樹最長輕鏈長度為k-1的概率，

h[k]=(fs*g[k]%mod+gs*f[to2][k-1]%mod-gs*fs+mod)%mod;

?

只是x與to2相連的這條邊為輕鏈所以有減1，值得提醒的一點是這里的f[x][k]并不是最終的f[x][k]，只是考慮到當前幾個兒子時的值，一個兒子一個兒子地向里加。考慮到f數組直接改的話會錯，所以用h數組保存，最后加到g數組中清空h，當to1為重兒子這個情況考慮玩后將g數組加到f中去，清空g。當前節點x求完后，此時的f數組并不是前綴和，所以需要再次轉化。

最后求答案時再次將前綴和轉化為單個的值

至于此題為啥求概率卻用一堆整數想乘是因為題目要求

我們發現每一層的1/chu[x]即為分母，所以可以直接乘逆元，而這樣的相加不會影響結果

所以最后i*f[x][i]就是期望。

?

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<string> 5 #include<algorithm> 6 #include<vector> 7 #include<cmath> 8 #include<stack> 9 #include<queue> 10 #define MAXN 3101 11 #define ll long long 12 using namespace std; 13 const ll mod=1e9+7; 14 struct node{ll to,n;}e[MAXN]; 15 ll head[MAXN],tot; 16 void add(ll u,ll v){e[++tot].to=v;e[tot].n=head[u];head[u]=tot;} 17 ll size[MAXN]; 18 ll f[MAXN][MAXN],g[MAXN],h[MAXN]; 19 ll n;ll chu[MAXN]; 20 ll pow(ll x,ll y) 21 { 22 ll ans=1; 23 while(y) 24 { 25 if(y&1)ans=(ans*x)%mod; 26 x=(x*x)%mod; 27 y>>=1; 28 } 29 return ans%mod; 30 } 31 void DFS(ll x) 32 { 33 size[x]=1; 34 for(ll i=head[x];i;i=e[i].n) 35 { 36 ll to=e[i].to; 37 DFS(to); 38 size[x]+=size[to]; 39 } 40 ll ppow=pow(chu[x],mod-2ll)%mod; 41 for(ll i=head[x];i;i=e[i].n) 42 { 43 for(ll i=0;i<=size[x]+1;++i)g[i]=1; 44 for(ll j=head[x];j;j=e[j].n) 45 { 46 ll fs,gs; 47 ll to1=e[i].to;ll to2=e[j].to; 48 for(ll k=0;k<=size[to2]+1;++k) 49 { 50 if(to1==to2){ 51 if(!k)fs=f[to2][k];else fs=f[to2][k]-f[to2][k-1]; 52 if(!k)gs=g[k]; else gs=g[k]-g[k-1]; 53 h[k]=(fs*g[k]%mod+gs*f[to2][k]%mod-gs*fs+mod)%mod; 54 // printf("h[%lld]=%lld\n",k,h[k]); 55 } 56 else if(k){ 57 if(!k)fs=f[to2][k-1];else fs=f[to2][k-1]-f[to2][k-2]; 58 if(!k)gs=g[k]; else gs=g[k]-g[k-1]; 59 h[k]=(fs*g[k]%mod+gs*f[to2][k-1]%mod-gs*fs+mod)%mod; 60 } 61 } 62 g[0]=h[0];h[0]=0; 63 for(ll k=1;k<=size[to2]+1;++k) 64 { 65 g[k]=(g[k-1]+h[k])%mod;h[k]=0; 66 } 67 } 68 for(ll j=size[x]+1;j>=1;--j) 69 { 70 g[j]=(g[j]-g[j-1]+mod)%mod;//printf("g[%lld]=%lld\n",j,g[j]); 71 } 72 for(ll j=0;j<=size[x]+1;++j) 73 { 74 f[x][j]=(f[x][j]+g[j]*ppow%mod)%mod; 75 // printf("f[%lld][%lld]=%lld\n",x,j,f[x][j]); 76 } 77 // printf("p=%lld\n",pow(chu[x],mod-2ll)); 78 } 79 if(head[x]==0)f[x][0]=1; 80 for(ll i=1;i<=size[x]+1;++i) 81 { 82 f[x][i]=(f[x][i]+f[x][i-1]+mod)%mod; 83 // printf("f[%lld][%lld]=%lld\n",x,i,f[x][i]); 84 } 85 } 86 ll ru[MAXN];ll si=1; 87 int main() 88 { 89 scanf("%lld",&n); 90 for(ll i=1;i<=n;++i){ 91 scanf("%lld",&chu[i]); 92 for(ll j=1;j<=chu[i];++j){ 93 ll y; 94 scanf("%lld",&y); 95 add(i,y);ru[y]++; 96 } 97 } 98 ll root=0; 99 for(ll i=1;i<=n;++i){ 100 if(ru[i]==0) 101 root=i; 102 } 103 DFS(root); 104 ll ans=0; 105 for(ll i=1;i<=size[root]+1;++i) 106 { 107 ans=(ans+i*(f[root][i]-f[root][i-1]%mod)+mod)%mod; 108 } 109 printf("%lld\n",(ans+mod)%mod); 110 } View Code

?

轉載于:https://www.cnblogs.com/Wwb123/p/11191427.html

總結

以上是生活随笔為你收集整理的B. 熟练剖分(tree) (概率DP)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。