给出一个 \(n\) 个点的有根树，每个数上有一个值，范围是 \([0,b_i]\) 中的实数。
求这个树是 heap 的概率（父节点值 < 子节点值）。
\(1\leq n\leq 300, 1\leq b_i\leq 10^9\)
非常有意思的题目！
最简单的想法是 \(f(i,j)\) 表示当前节点为 \(i\) ，值为 \(j\) 的概率，但是 \(j\) 的范围在 \(10^9\) 级别，很难的啦。
那考虑如果没有数值限制呢？所有的点范围都是 \([0,x]\) 呢？
这个时候发现只需要关注相互关系就可以了，观察到实数范围内，两个数相同的概率为 \(0\)，所以只要关注这 \(n\) 个点的相互关系有多少种。
什么叫做相互关系？就是从小到大给树里面的点排序，有多少种合法的排列方法。
此时考虑的状态就是 \(f(i)\) 表示当前的节点为 \(i\) ，子树内的点有多少种排列方法。
最后 heap 的概率就是 \(\frac{f(root)}{n!}\).
但是现在发现还有另外一个要求，就是所有点的数值范围可能不一样。
首先考虑一个非常朴实的点，就是子树根节点的 \(b_{root}\) 要小于等于子树内所有的 \(b_{son}\) ，可以预处理干这个。
如果 \(b_{root}=b_{son}\) 一切都好说，就是上述分析的点，但是如果 \(b_{root}<b_{son}\) 呢？
仔细观察发现，子树中的值可以在 \([0,b_{root}]\) 也可以在 \([b_{root}, b_{son}]\) 里面，此时面临两个选择。
有一个 idea 就是可以考虑多加上一维度，\(f(i,j)\) 表示当前节点为 \(i\) ，在 \([0,b_i]\) 中有 \(j\) 个子节点的排列方法。
此时有两种情况,
-
\(b_{root} = b_{son}\)
\(g(root,i)\) += \(f(son,j)\times f(root, j-i)\times \frac{(b_{son}-b_{root})^{j-i}}{(j-i)!}\)
-
\(b_{root}<b_{son}\)
\(g(root,i)+=f(son,j)\times f(root,j-i)\times\binom{i}{j}\)
最后的答案是 \(\frac{\sum_{i=0}^{n} f(root,i)\times\frac{1}{i!}}{\prod b_i}\).
时间复杂度 : \(O(n^3)\)
空间复杂度 : \(O(n^3)\)
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=305;
const int mod=1e9+7;
int n,m=0,rt;
vector<int>son[N];
map<int,int>Map;
int p[N],a[N],b[N],val[N],pp[N][N][N],pw[N],ipw[N],invp[N][N],C[N][N];
int Power(int x,int k){if(k==0)return 1;int val=Power(x,k>>1);val=1ll*val*val%mod;if(k&1)val=1ll*val*x%mod;return val;
}
void get_a(int x){for(auto to:son[x]){get_a(to);a[x]=min(a[x],a[to]);}
}
int dp[N][N],f[N],g[N],h[N],sz[N];
void dfs(int x){for(auto to:son[x])dfs(to);memset(g,0,sizeof(g));g[0]=1;sz[x]=0;
// cerr<<"x="<<x<<endl;for(auto to:son[x]){memset(h,0,sizeof(h));memset(f,0,sizeof(f));if(a[to]>a[x]){for(int i=0;i<=sz[to];i++)for(int j=i;j<=sz[to];j++){h[i]+=1ll*dp[to][j]*pp[a[x]][a[to]][j-i]%mod;h[i]%=mod;}
// cerr<<dp[to][1]<<","<<pp[a[x]][a[to]][1]<<","<<invp[a[to]][1]<<endl;}else{for(int i=0;i<=sz[to];i++){h[i]+=dp[to][i];h[i]%=mod;}}
// cerr<<"h:";
// for(int i=0;i<=sz[to];i++)cerr<<h[i]<<" ";cerr<<endl;for(int i=0;i<=sz[x];i++)for(int j=0;j<=sz[to];j++){
// if(i+j==1)cerr<<i<<","<<j<<","<<g[i]<<","<<h[j]<<","<<C[i+j][j]<<" "; f[i+j]+=1ll*g[i]*h[j]%mod*C[i+j][i]%mod;f[i+j]%=mod;}
// cerr<<endl;
// cerr<<"f:";
// for(int i=0;i<=sz[x]+sz[to];i++)cerr<<f[i]<<" ";cerr<<endl;sz[x]+=sz[to];swap(f,g);}
// cerr<<endl;// for(int i=0;i<=sz[x];i++)cerr<<g[i]<<" ";cerr<<endl;for(int i=0;i<=sz[x];i++){dp[x][i+1]+=g[i];dp[x][i+1]%=mod; }sz[x]++;
}
signed main(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i]>>p[i];b[i]=a[i];son[p[i]].push_back(i);if(!p[i])rt=i;}for(int i=1;i<=n;i++)Map[a[i]]=1;Map[0]=1;for(auto&it:Map){val[m]=it.first,it.second=m++;
// cerr<<it.first<<","<<it.second<<" ";}
// cerr<<endl;
// for(int i=1;i<=n;i++)cerr<<a[i]<<" ";cerr<<endl;for(int i=1;i<=n;i++)a[i]=Map[a[i]];
// for(int i=1;i<=n;i++)cerr<<a[i]<<" ";cerr<<endl;pw[0]=1;for(int i=1;i<=n;i++)pw[i]=1ll*pw[i-1]*i%mod;for(int i=0;i<=n;i++)ipw[i]=Power(pw[i],mod-2);for(int i=0;i<=m;i++)for(int j=i+1;j<=m;j++){pp[i][j][0]=1;for(int k=1;k<=n;k++)pp[i][j][k]=1ll*pp[i][j][k-1]*(val[j]-val[i])%mod;}for(int i=1;i<=m;i++){invp[i][0]=1;for(int k=1;k<=n;k++){invp[i][k]=Power(pp[0][i][k],mod-2); }}for(int i=0;i<=m;i++)for(int j=i+1;j<=m;j++)for(int k=0;k<=n;k++){pp[i][j][k]=1ll*pp[i][j][k]*ipw[k]%mod;}C[0][0]=1;for(int i=1;i<=n;i++){C[i][0]=1;for(int j=1;j<=i;j++){C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;}}get_a(rt);
// for(int i=1;i<=n;i++)cerr<<a[i]<<" ";cerr<<endl;dfs(rt);
// for(int i=1;i<=n;i++)cerr<<sz[i]<<" ";cerr<<endl;
// for(int i=0;i<=sz[2];i++)cerr<<dp[2][i]<<" ";cerr<<endl;int ans=0;
// for(int i=0;i<=sz[rt];i++)cerr<<dp[rt][i]<<" ";cerr<<endl;for(int i=0;i<=sz[rt];i++){cerr<<dp[rt][i]<<","<<pp[0][a[rt]][i]<<" ";ans+=1ll*dp[rt][i]*pp[0][a[rt]][i]%mod;ans%=mod;}cerr<<endl;
// cerr<<"ans="<<ans<<endl;for(int i=1;i<=n;i++){
// cerr<<Power(val[a[i]],mod-2)<<" ";ans=1ll*ans*Power(b[i],mod-2)%mod;ans%=mod;}
// cerr<<endl;cout<<ans<<endl;
// cerr<<1ll*ans*12%mod*Power(7,mod-2)%mod<<endl;return 0;
}
/*
3
1 0
1 1
1 1
*/
/*
2
1 0
2 1
*/
/*
2
1 0
1 1
*/
/*
3
1 0
2 1
2 1
*/
/*
13
1 0
2 1
2 1
4 2
5 2
10 3
9 3
6 4
10 8
10 1
10000000 8
99999999 7
12 12
*/
/*
2
2 0
1 0
*/