[期望DP][树形DP]JZOJ 5233 概率博弈

Description

小A和小B在玩游戏。这个游戏是这样的：
有一棵n个点的以1为根的有根树，叶子有权值。假设有m个叶子，那么树上每个叶子的权值序列就是一个1->m 的排列。
一开始在1号点有一颗棋子。两人轮流将这颗棋子移向其当前位置的一个儿子。假如棋子到达叶子，游戏结束，最终获得的权值为所在叶子对应权值。
小A希望最后的权值尽量大，小B希望尽量小。小A是先手。
在玩了很多局游戏后，小B对其中绝大多数局游戏的结果不满意，他觉得是小A对叶子权值做了手脚。于是他一怒之下，决定将叶子的权值随机排列。现在小B想知道，假如叶子的权值是随机排列的（即叶子权值的每种排列都以等概率出现），那么游戏期望的结果是多少？
请输出答案乘上m! 对10^9+7取模的结果，显然这是一个整数。

 

Input

输入文件名为game.in。
第一行包含一个整数n。
接下来n-1行，每行两个整数u,v，表示有一条连接节点u,v的边。

Output

输出文件名为game.out。
输出一个整数，表示答案。

 

Sample Input

输入1：
5
1 2
2 3
1 4
2 5

输入2：
10
10 7
7 6
10 2
2 3
3 8
3 1
6 9
7 5
1 4

Sample Output

输出1：
14

输出2：
74

 

Data Constraint

对于10%的数据，n<=5
对于30%的数据，n<=10
对于60%的数据， n<=50
对于100%的数据，n<=5000,保证给出的是一棵合法的树。

分析

我们发现如果要直接按权值求方案未免太难，我们不妨设最终答案为x，则小于等于x的权值设为0，大于的设为1

设f[i][j][0/1]为在以i为根的子树中，有j个叶子节点为0，且i选择到的是0/1的期望

那么转移是比较显然的，可以用一个DFS枚举从子节点传上来的叶子数量再转移（O(n)复杂度）

然后对于层数我们显然小A或小B一定只会取1或0，那么另一个怎么求呢？我们只需要求出当前j与子树内叶子总数的组合数再-得到的情况即可

最后我们统计答案时还需要考虑排列，所以需要乘上i!*(sz-i)!

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int N=5e3+10;
const ll P=1e9+7;
struct Edge {
    int u,v,nx;
}g[2*N];
int cnt,list[N],sz[N],a[N];
ll f[N][N][2],fact[N],ans;
int n,m,size;

void Add(int u,int v) {
    g[++cnt]=(Edge){u,v,list[u]};list[u]=cnt;
}

ll Power(ll x,ll y) {ll ans=1ll;for (;y;y>>=1,(x*=x)%=P) if (y&1) (ans*=x)%=P;return ans;}

ll C(ll n,ll m) {return fact[n]*Power(fact[m],P-2)%P*Power(fact[n-m],P-2)%P;}

void DFS(int dep,int u,int now,int cont,ll e) {
    if (dep>size) {(f[u][cont][now]+=e)%=P;return;}
    for (int i=0;i<=sz[a[dep]];i++) if (f[a[dep]][i][now]) DFS(dep+1,u,now,cont+i,e*f[a[dep]][i][now]%P);
}

void DFS(int u,int fa,int dep) {
    for (int i=list[u];i;i=g[i].nx) if (g[i].v!=fa) DFS(g[i].v,u,!dep),sz[u]+=sz[g[i].v];
    size=0;for (int i=list[u];i;i=g[i].nx) if (g[i].v!=fa) a[++size]=g[i].v;
    if (sz[u]) {
        DFS(1,u,dep,0,1ll);
        for (int i=0;i<=sz[u];i++) f[u][i][!dep]=((C(sz[u],i)-f[u][i][dep])%P+P)%P;
    }
    else sz[u]=1,f[u][0][0]=f[u][1][1]=1;
}

int main() {
    freopen("game.in","r",stdin);
    freopen("game.out","w",stdout);
    scanf("%d",&n);
    fact[0]=1ll;
    for (int i=1;i<N;i++) fact[i]=1ll*fact[i-1]*i%P;
    for (int i=1,u,v;i<n;i++) scanf("%d%d",&u,&v),Add(u,v),Add(v,u);
    DFS(1,0,0);for (int i=0;i<=sz[1];i++) (ans+=f[1][i][1]*fact[i]%P*fact[sz[1]-i]%P)%=P;
    printf("%lld",ans);
}