题目

题目大意

给你一棵树，这棵树上的所有叶子节点的权值是随机的排列。
两个人博弈，从根开始，轮流往下走。
先手希望权值最大，后手希望权值最小。
问期望的最终结果。

思考历程

这场比赛实在是太丧心病狂了！两个期望题，有没有人性啊！
还是那种特别变态的期望……
想了好久，没有想出来……
于是打暴力：
枚举所有的排列，然后用DP计算答案。
如果喜欢，DP可以加上alpha-beta剪枝……当然我没加，因为在这题里面没有什么意义。
分数还给的挺大方的，30分。

正解

首先推个式子：
$$\begin{gathered} E(x) \\ =\sum xP(x=ans) \\ =\sum P(x\le ans) \end{gathered}$$
后面这个是什么鬼？
我们将第二个式子拆开，对于$x$，它贡献了$x$个$P(ans=x)$。
看看第三个式子，对于$x^{\prime }\le x$，它就可以加上$x$的贡献。这样的$x^{\prime }$有$x$个，所以这是成立的。

接下来就是一个很巧妙的转化：
我们设结果为$x$，将大于$x$的记作$1$，将小于等于$x$的记作$0$。
这样就大大地简化了题目，因为我们只需要关心它的结果是否为$1$，而不需要关心结果是否恰好为$x$。
然后就是树形DP：设$f_{i,j,0/1}$表示点$i$为根的子树中，叶子节点的权值为$0$的个数是$j$，点$i$的值为$0$或$1$（从下面转移上来的值）的方案数。
方程就不用说了吧……自己推。
这就是一个树上背包问题。
至于最终的答案，枚举$x$，它的贡献就是$\frac{f_{1,x,1}}{C_m^x}$。（$m$为叶子节点的个数）
由于题目良心地让我们输出$ans\ast m!$，所以说，输出的就是$f_{1,x,1}\ast x!\ast (m-x)!$

然而这个算法看上去是$O(n^3)$的，我在很长时间内也这么认为。
YMQ：我吸一口臭氧，也能过！
但时间复杂度实际上是$O(n^2)$。
为什么？
从最简单的开始考虑：如果这棵树是一棵二叉树，对于一个非叶子节点，当大小分布比较均匀时：
对于根节点，合并子树的时间是${\left(\frac{n}{2}\right)}^2=\frac{n^2}{4}$。
对于下一层，时间是$2{\left(\frac{n}{4}\right)}^2=\frac{n^2}{8}$。
再下一层，时间是$4{\left(\frac{n}{8}\right)}^2=\frac{n^2}{16}$。
后面的就不枚举了。
把它们全部加起来，时间就趋近于$\frac{n^2}{2}$。
当大小分布不均匀时，我们考虑最极端的情况，时间复杂度还是$O(n^2)$。
至于不均匀而又不极端的情况……感性理解，不信邪的可以打一个DP来求最坏的情况。
考虑一下多叉树，发现其实际上是类似的，时间复杂度是$O(n^2)$。
最终我还是不会证明……

代码

using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 5000
#define mo 1000000007
int n;
struct EDGE{int to;EDGE *las;
} e[N*2+1];
int ne;
EDGE *last[N+1];
inline void link(int u,int v){e[++ne]={v,last[u]};last[u]=e+ne;
}
long long jc[N+1];
int tot[N+1];
long long f[N+1][N+1][2];
void dfs(int x,int fa,bool flag){if (last[x]->las==NULL && last[x]->to==fa){//叶子节点的情况tot[x]=1;f[x][0][1]=f[x][1][0]=1;return;}EDGE *ei=last[x];//另外处理第一个儿子，这样就不用考虑初始化if (ei->to==fa)ei=ei->las;dfs(ei->to,x,!flag);memcpy(f[x],f[ei->to],sizeof f[ei->to]);tot[x]=tot[ei->to];ei=ei->las;if (flag==0){for (;ei;ei=ei->las)if (ei->to!=fa){dfs(ei->to,x,1);for (int j=tot[x]+tot[ei->to];j>=0;--j){//k=0f[x][j][1]=(f[x][j][0]*f[ei->to][0][1]%mo+f[x][j][1]*f[ei->to][0][0]%mo+f[x][j][1]*f[ei->to][0][1]%mo)%mo;f[x][j][0]=f[x][j][0]*f[ei->to][0][0]%mo;for (int k=1;k<=tot[ei->to] && k<=j;++k){(f[x][j][1]+=(f[x][j-k][0]*f[ei->to][k][1]%mo+f[x][j-k][1]*f[ei->to][k][0]%mo+f[x][j-k][1]*f[ei->to][k][1]%mo))%=mo;(f[x][j][0]+=f[x][j-k][0]*f[ei->to][k][0])%=mo;}}tot[x]+=tot[ei->to];}}else{for (;ei;ei=ei->las)if (ei->to!=fa){dfs(ei->to,x,0);for (int j=tot[x]+tot[ei->to];j>=0;--j){//k=0f[x][j][0]=(f[x][j][0]*f[ei->to][0][0]%mo+f[x][j][0]*f[ei->to][0][1]%mo+f[x][j][1]*f[ei->to][0][0]%mo)%mo;f[x][j][1]=f[x][j][1]*f[ei->to][0][1]%mo;for (int k=1;k<=tot[ei->to] && k<=j;++k){(f[x][j][0]+=(f[x][j-k][0]*f[ei->to][k][0]%mo+f[x][j-k][0]*f[ei->to][k][1]%mo+f[x][j-k][1]*f[ei->to][k][0]%mo))%=mo;(f[x][j][1]+=f[x][j-k][1]*f[ei->to][k][1])%=mo;}}tot[x]+=tot[ei->to];}}
}
int main(){freopen("game.in","r",stdin);freopen("game.out","w",stdout);scanf("%d",&n);jc[0]=1;for (int i=1;i<=n;++i)jc[i]=jc[i-1]*i%mo;for (int i=1;i<n;++i){int u,v;scanf("%d%d",&u,&v);link(u,v),link(v,u);}dfs(1,0,0);long long ans=0;for (int i=0;i<=tot[1];++i)ans=(ans+f[1][i][1]*jc[i]%mo*jc[tot[1]-i]%mo)%mo;printf("%lld\n",ans);return 0;
}

总结

这道题有一个·很奇妙的思想，就在于$\sum xP(x=ans)=\sum P(x\le ans)$。
。
通过这个东西，可以大大地简化题目。
当条件为“等于”的时候，我们可以试着转化成“大于”“小于”。
然后就是树上背包的时间复杂度……