看到\(k\)次幂求和先用斯特林数拆幂：\(x^k = \sum\limits_{i=1}^k \binom{x}{k}\left{ \begin{array} i \\ k \end{array} \right}i!\)。
那么原式等于\(\sum\limits_{X} \sum\limits_{i=1}^k \binom{f(X)}{k}\left{ \begin{array} i \\ k \end{array} \right}i! = \sum\limits_{i=1}^k \left{ \begin{array} i \\ k \end{array} \right}i! \sum\limits_{X} \binom{f(X)}{k}\)。
那么我们需要求\(\sum\limits_{X} \binom{f(X)}{k}\)，它的组合意义就是从点集\(X\)的斯坦纳树中无序选出\(k\)条边的方案总数。不难发现这个就可以背包了。
设\(f_{i,j}\)表示在斯坦纳树经过点\(i\)的所有点集中选择\(j\)条边的方案数。当一个儿子转移上来的时候分三种情况转移：
1、不选择这一个子树；
2、只选择这一棵子树，此时需要考虑这棵子树到当前点的边；
3、同时选择当前点的其他子树（或者当前点）和这一棵子树，此时需要考虑这棵子树到当前点的边。
值得注意的是只有在计算3的时候才能够贡献答案，因为1在之前已经贡献过答案了，而2只是某一棵子树向上延伸的结果，实际上并没有找到一个合法的斯坦纳树，所以不能贡献答案。
然后又把模数写成了998244353
CF1097G Vladislav and a Great Legend 组合、树形背包
原文：https://www.cnblogs.com/Itst/p/10836348.html