ARC130D

· · 题解

显然问题相当于要把整棵树重标号。

首先有一个粗略的观察：一个点要么小于其所有的邻居，要么大于其所有的邻居。我们下文称这两类点分别为大点与小点。

此时我们可能会想到钦定某个点是大点/小点。不过一个比较显然的事实是大点周围只会有小点，小点周围只会有大点，结合树是一张二分图可以得到大小点的分配方案本质上是树的一个黑白染色，可以对于每种黑白染色方案分别计算。

一个尝试就是考虑从 1 到 n 依次把标号填在树上的节点，小点必须是其与其邻居中第一个填的，大点必须是其与其邻居中最后一个填的。但是感觉这么考虑没有前途，毕竟太“全局观”了，不利于树上 DP 优化。

我们想一下怎么通过子树合并的角度来考虑。注意到子树间的合并本质上只是标号重新分配，转移只依赖子树 sze，而方案的合法性只取决于相对大小。

于是可以令 dp_{u,i} 为 u 号点在子树中排名为 i 的方案数。初始有 dp_{u,1}=1。

以钦定 u 为极大点为例，则转移：

dp_{u,i+j} \leftarrow dp_{u,i}\binom{i-1+j}{i-1}\binom{sze_u-i+sze_v-j}{sze_u-i} \sum \limits_{k=1}^{j} dp_{v,j}

意义则为枚举 v 子树中比 u 小的有多少个节点，然后再枚举 v 的排名。前缀和优化即可做到树上背包的 O(n^2)。