题目链接:D. Tree Array
题解:参考官方题解
简单解释一下,固定最开始的根节点,然后考虑每一对数值a,b对答案的贡献,假定a<b,那a比b 先被选出的概率为多少呢,
用dp[i][j]表示有两个栈大小分别i,j,在这两个栈有相同概率被取走一个数的情侣下,i这个栈先比j取完的概率,
转移方程在上面英文题解中。
然后求和每对a,b的贡献,最后除N就是答案
#include<bits/stdc++.h> #define pb push_back #define ll long long using namespace std; #define fab 1e-9 const int mod=1e9+7; const int N=2e2+5; vector<int>g[N]; int n,dp[N][N],dep[N],fa[N][9];//dp[i][j]表示i先比j选完的概率 ll poww(ll x,ll k) { ll t=1; while(k) { if(k%2) { t=(t*x)%mod; } x=(x*x)%mod; k/=2; } return t; } void dfs(int v,int d,int f) { dep[v]=d; fa[v][0]=f; for(int x:g[v]) { if(x==f)continue; dfs(x,d+1,v); } } int lca(int x,int y) { if(dep[x]<dep[y])swap(x,y); int k=dep[x]-dep[y]; for(int i=8;i>=0;i--) { if(k>>i&1) { x=fa[x][i]; } } if(x==y)return x; for(int i=8;i>=0;i--) { if(fa[x][i]!=fa[y][i]) { x=fa[x][i];y=fa[y][i]; } } return fa[x][0]; } void init() { for(int i=1;i<9;i++) { for(int j=1;j<=n;j++) { fa[j][i]=fa[fa[j][i-1]][i-1]; } } } int main() { scanf("%d",&n); for(int i=0;i<n-1;i++) { int x,y; scanf("%d %d",&x,&y); g[x].pb(y); g[y].pb(x); } for(int i=1;i<=n;i++)dp[0][i]=1; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { dp[i][j]=1ll*(dp[i-1][j]+dp[i][j-1])*poww(2,mod-2)%mod; } } int ans=0; for(int i=1;i<=n;i++) { dfs(i,0,i); init(); for(int j=1;j<=n;j++) { for(int k=j+1;k<=n;k++) { int lc=lca(j,k); int dep_j=dep[j]-dep[lc]; int dep_k=dep[k]-dep[lc]; ans=(ans+dp[dep_k][dep_j])%mod; } } } ans=ans*poww(n,mod-2)%mod; cout<<ans<<endl; return 0; }