题意简述：一棵 \(n\) 个点的有根树，随机一个 \([1, n]\) 的排列作为每个点的点权。定义一个点为 “好点”，当且仅当它是它到根节点路径上的点权最大的点。设一棵树的 “好点” 个数为 \(c\)，则它的价值为 \(k^c\)，其中 \(k\) 是一个常数。求这棵树的期望价值。\(1\leq n\leq 5000\)。
对于树上的排列计数，我们往往有两种方式：从根向叶填数和从叶向根填数。对于这道题，由于它的定义涉及到了节点到根的路径，第二种方式较为不便，我们可以尝试第一种方式。
然而树形dp的基本形式限制了我们无法在dp到某棵子树时记录它祖先的状态（因为这样就无法正常合并子树）。
因此，我们考虑在dp到某个子树时，将祖先的位置预留。设 \(i\) 点的点权为 \(a_i\)，它在树上的父亲为 \(fa_i\)， \(f_{i, j}\) 表示以 \(i\) 为根的子树中，有 \(j\) 个点 \(\{u_1, u_2, \ldots, u_j\}\) 满足 \(\forall a_u > \max_{v\in \rm{path}(fa_i, \rm{root})}a_v\) 的所有填数方法的价值和，不妨称之为 “半好点”。注意这里的定义并非代表子树中有 \(j\) 个 “好点”，但是显然 “好点” 个数不会超过 \(j\)。
简单分析一下就可以得到，在 \(f_{i, j}\) 包含的任意一个方案中，点权最大的 \(j\) 个点必然是这 \(j\) 个 “半好点” 。因为如果 \(i\) 为根的子树中存在两个点 \(u, w\) 满足 \(a_u < a_w\) 且 \(u\) 为 “半好点”，则必然有 \(a_w > \max_{v\in \rm{path}(fa_i, \rm{root})}a_v\)，即 \(w\) 必然也是 “半好点”。
因此我们可以进行转移了。对于以 \(i\) 为根的子树，我们初始时只有一个空集，即 \(f_{i, j}=[j==0]\)。
依次合并各个子树，由于子树间的大小关系相互独立，我们只需要确定不同子树间元素的大小关系即可。设 \(sz_i\) 为子树 \(i\) 的点数，且我们当前正在合并子树 \(u\)，那么 \(\frac{f'_{i, j}}{j!(sz'_i-j)!}=\sum_{w+v=j} \frac{f_{i, w}}{w!\cdot (sz_i-w)!}\cdot \frac{f_{u, v}}{v!\cdot(sz_u-v)!}\)。这里阶乘的意义是多重集的全排列，即，将来自同一棵子树的点看做相同元素，分别对 \(j\) 个 “半好点” 和 \(sz'_i-j\) 个剩余的点进行排列的方案数。复杂度为树上背包的复杂度，即 \(O(n^2)\)。
合并完子树后，我们需要考虑根节点的取值情况，即在子树组成的排列中插入 \(i\) 点的取值。对于此时的 \(f_{i, j}\)，我们已知的是有 \(j\) 个点 \(u\) 满足 \(a_u > \max_{v\in \rm{path}(i, \rm{root}) a_v}\)，因此将 \(i\) 点插入时，我们显然不能将 \(i\) 插入到最大的 \(j\) 个元素后面。
当 \(i\) 是 “半好点” 的时候，显然它只能被插入到第 \(j\) 大的元素前面，第 \(j+1\) 大的元素后面的位置。此时 “半好点” 个数会至少增长 \(1\)，且 \(i\) 必然为 “好点”。考虑一个 \(a_u < a_i\)，显然此前 \(u\) 不为 “半好点”，但 \(u\) 也可能满足 \(a_u > \max_{v\in \rm{path}(fa_i, \rm{root})} a_v\)，从而成为新的 “半好点”。注意由非 “半好点” 转化为 “半好点” 的权值是单调的，即只有权值最大的若干非 “半好点” 可能转化为 “半好点”，因此转化的方式是唯一的。
当 \(i\) 不是 “半好点” 的时候，它有 \(sz_i-j\) 个位置可以插入，并且不会造成任何额外的影响。
因此我们得到了最终的转移：
\[f'_{i, j}=\sum_{u=0}^{j-1} f_{i, u}\cdot k+f_{i, j}\cdot (sz_i-j)\]
用前缀和优化，复杂度 \(O(n^2)\)，最终答案为 \(f_{\rm{root}, n}\)。
#include <bits/stdc++.h>
#define R register
#define ll long long
#define mp make_pair
#define pii pair<int, int>
using namespace std;
const int N = 5100, M = N << 1, mod = 998244353;
int n, k, hd[N], to[M], nxt[M], noedg = 1, size[N];
ll f[N][N], fac[N], inv[N], tmp[N];
inline void addEdg(int x, int y) {
nxt[++noedg] = hd[x], hd[x] = noedg, to[noedg] = y;
nxt[++noedg] = hd[y], hd[y] = noedg, to[noedg] = x;
return;
}
template <class T>
inline void read(T &x) {
x = 0;
char ch = getchar(), w = 0;
while (!isdigit(ch)) w = ch == '-', ch = getchar();
while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
x = w ? -x : x;
return;
}
void dfs(int now, int fa) {
f[now][0] = 1;
for (R int i = hd[now], v; i; i = nxt[i]) {
if ((v = to[i]) == fa) continue;
dfs(v, now);
for (R int j = size[now]; ~j; --j) {
for (R int k = size[v]; k; --k)
f[now][j + k] = (f[now][j + k] + f[now][j] * f[v][k]) % mod;
f[now][j] = f[now][j] * f[v][0] % mod;
}
size[now] += size[v];
}
++size[now], tmp[0] = 0;
for (R int i = 0; i < size[now]; ++i) {
f[now][i] = f[now][i] * fac[i] % mod * fac[size[now] - i - 1] % mod;
tmp[i] = ((i ? tmp[i - 1] : 0) + f[now][i]) % mod;
}
tmp[size[now]] = tmp[size[now] - 1];
for (R int i = size[now]; i; --i)
f[now][i] = (tmp[i - 1] * k + f[now][i] * (size[now] - i)) % mod * inv[i] % mod * inv[size[now] - i] % mod;
f[now][0] = 1;
return;
}
inline ll quickpow(ll base, ll pw) {
ll ret = 1;
while (pw) {
if (pw & 1) ret = ret * base % mod;
base = base * base % mod, pw >>= 1;
}
return ret;
}
int main() {
int x, y;
read(n), read(k);
for (R int i = 1; i < n; ++i)
read(x), read(y), addEdg(x, y);
fac[0] = 1;
for (R int i = 1; i <= n; ++i)
fac[i] = fac[i - 1] * i % mod;
inv[n] = quickpow(fac[n], mod - 2);
for (R int i = n; i; --i)
inv[i - 1] = inv[i] * i % mod;
dfs(1, 0);
cout << f[1][n] * fac[n] % mod << endl;
return 0;
}原文：https://www.cnblogs.com/suwakow/p/11802969.html