树上容斥

这题比较抽象，为了防止造成二次疑惑，请不要自己再去思考，还是老老实实看题解吧。

题目大意：给一个$n(n\le5000)$个点的树，根是1，定义好点是一个从他到根的路径上没有点权值比他大的点，一个树的权值是$k(k<998244353)$的$c$次方，即$k^c$，给点赋的权值恰好是$n$的排列，问树的权值的期望乘上$n!$。

首先这肯定是个树形$dp$，那咋做？

定义状态$f_{x,i}$为点$x$的子树中最小的为好点的点的相对大小是$i$时，这棵子树的贡献。

转移是平凡的，先把子树一个一个合并，具体就是根据定义插起来统计，牢记第二个状态的含义是做贡献的最小的是第几小就行，最后再插入这棵子树的树根，如果他做了贡献，那他一定是这棵子树里做贡献的最小的点，如果没有，那他一定小于这棵子树里做贡献的最小的点。

看起来好像就完事了，但事实上，他会出问题，我们会发现，我们钦定一个点不会做贡献不代表他一定不会做贡献，所以我们实际上会重复统计一个合法状态的所有子集状态。

形象一点，我们的$dp$数组的下标虽然是做贡献的最小的是第几小，但实际上他还是会存下来一些最小的做贡献的点比下标还小的，只不过这种说法虽然好理解却不如前面那种说法好利用。

那有妹有办法使他只统计自己的贡献而不多统计子集呢，答案是我不知道，但是我们实际上可以把子集的贡献通过转换变成之前的准确的自己的贡献。

有这么一个东西：$$k^c=\sum_{i=0}^{c}{C_c^i(k-1)^i}$$
证明如下：

$k^c=((k-1)+1)^c$

由二项式定理：

$((k-1)+1)^c=\sum_{i=0}^{c}{C_c^i(k-1)^{c-i}}$

又因为$C_n^m=C_n^{n-m}$
所以：

$\sum_{i=0}^{c}{C_c^i(k-1)^{c-i}}=\sum_{i=0}^{c}{C_c^i(k-1)^{i}}$

证毕。

不过这东西有啥用处嘞？

其实可以发现外层的$\sum_{i=0}^{c}$就是在枚举这个大小为$c$的点集的子集大小，而$C_c^i$则是表示这样大小的子集有多少个，这下就可以光明正大的把一个状态的子集全算一遍了，只需要把贡献里的$k$变成$k-1$即可。