妈耶，改这题各种失误，清空都能清错，本来清x然后清空了儿子，服了。 区间题做多了下意识leaf[1]-i+1 服气。 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,保证给出的是一棵合法的树。
wwtdalao的题目。 据gjx大爷说是经典题= =，很常见的套路。 就是在树上dp，问了hhh才切，看来我还是很菜= = 首先贴个题解： 那么我们就可以直接dp了。 设f为图中的G。 那么我们先统计出每个节点为根的叶子结点个数，然后开始dp。 边界条件f[x][1][0]=f[x][0][1]=1，x为叶子。 对于当前结点x，枚举他的子节点（子树），进行合并。 枚举的第一个直接赋值，然后其他的合并分类讨论。 然后枚举i,j表示进行合并的两颗树中有多少个0，然后对于合并时相连的节点的0/1讨论。 如果dep[x]&1，由小A操作，那么只有x=0,y=0（连接的两个节点）时F[x]=0(注意是大F)否则都为1，因为是取max。 反之只有x=1,y=1的时候F[X]=1;因为是取min。 然后就可以直接更新了。 答案统计就是f[1][i][1]*fac[i]*fac[leaf[1]-i] 因为0和1的排列顺序不固定，所以用阶乘计算。
#include<cstdio> #include<algorithm> #include<cstring> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) using namespace std; const int N=5e3+5; const int mo=1e9+7; typedef long long ll; int n,m; int g[N][N][2],tot; int fa[N],leaf[N],fac[N]; bool bo[N]; int f[N][N][2],head[N],next[N<<1],go[N<<1]; inline void add(int x,int y) { go[++tot]=y; next[tot]=head[x]; head[x]=tot; } inline void dfs1(int x) { bool flag=1; for(int i=head[x];i;i=next[i]) { int v=go[i]; if (v!=fa[x]) { flag=0; fa[v]=x; dfs1(v); leaf[x]+=leaf[v]; } } if(flag)leaf[x]=1; bo[x]=flag; } inline void dfs(int x,int opt) { if(bo[x]) { f[x][1][0]=1; f[x][0][1]=1; return; } for(int i=head[x];i;i=next[i]) { int v=go[i]; if (v!=fa[x]) { dfs(v,1-opt); } } int num=0,sum=0; for(int i=head[x];i;i=next[i]) { int v=go[i]; if (v!=fa[x]) { num++; if (num==1)memcpy(f[x],f[v],sizeof(f[x])); else { fo(j,0,leaf[x])g[x][j][0]=g[x][j][1]=0; fo(k,0,leaf[v]) { fd(j,leaf[x],0) { if (j+k>leaf[x])continue; if (opt==0) { g[x][j+k][0]=(ll)(g[x][j+k][0]+1ll*f[v][k][0]*f[x][j][0]%mo)%mo; g[x][j+k][1]=(ll)(g[x][j+k][1]+1ll*f[v][k][0]*f[x][j][1]%mo)%mo; g[x][j+k][1]=(ll)(g[x][j+k][1]+1ll*f[v][k][1]*f[x][j][0]%mo)%mo; g[x][j+k][1]=(ll)(g[x][j+k][1]+1ll*f[v][k][1]*f[x][j][1]%mo)%mo; } else { g[x][j+k][0]=(ll)(g[x][j+k][0]+1ll*f[v][k][0]*f[x][j][0]%mo)%mo; g[x][j+k][0]=(ll)(g[x][j+k][0]+1ll*f[v][k][0]*f[x][j][1]%mo)%mo; g[x][j+k][0]=(ll)(g[x][j+k][0]+1ll*f[v][k][1]*f[x][j][0]%mo)%mo; g[x][j+k][1]=(ll)(g[x][j+k][1]+1ll*f[v][k][1]*f[x][j][1]%mo)%mo; } } } memcpy(f[x],g[x],sizeof(f[x])); } sum+=leaf[v]; } } } int main() { freopen("game.in","r",stdin); freopen("game.out","w",stdout); scanf("%d",&n); fo(i,1,n-1) { int x,y; scanf("%d%d",&x,&y); add(x,y); add(y,x); } dfs1(1); dfs(1,0); fac[0]=1; fo(i,1,N)fac[i]=1ll*fac[i-1]*i%mo; int ans=0; fo(i,0,leaf[1]) ans=(ans+1ll*fac[i]*f[1][i][1]%mo*fac[leaf[1]-i]%mo)%mo; printf("%d\n",ans); }