题目链接：【被和谐】
题目大意：对于一棵树$(V,E)$，对于$S\subset V$，$f(S)$为点集$S$的导出子图的边数。求$\sum_{S\subset V}f(S)^k$
这里的导出子图说的是，点集为S，边集为$\{(u,v)\in E|u,v\in S\}$的一个子图。
看到这个$k$次方，马上用斯特林数。
$$ans=\sum_{S\subset V}f(S)^k=\sum_{i=0}^ki!S(k,i)\sum_{S\subset V}{f(S)\choose i}$$
然后考虑怎么求后面那个式子。
这个式子表示在$S$的导出子图里面选$i$条边的方案数，然后就可以树形dp了
设$dp_{x,s,0/1}$表示在以$x$为根的子树内部，选择$s$条边，$x$是否$\in S$的答案。
在新加上一个$x$的子树$v$的时候，$S$只有原来和只有新的子树的情况直接加上就行。
还有合在一起的情况，设原来的子树有$j$条边，$v$里面有$k$条边。
则$$dp[x][j+k][0]+=(dp[v][k][0]+dp[v][k][1])*dp[x][j][0]$$$$dp[x][j+k][1]+=(dp[v][k][0]+dp[v][k][1]+[k\not= 0]dp[v][k-1][1])*dp[x][j][1]$$
上面那里为什么要加$dp[v][k-1][1]$呢？因为这时$x$和$v$都在点集里，可以选择$(x,v)$这条边。
注意合在一起的情况还要统计进答案里。
而且由于会出现贡献到自己的情况，所以要用一个辅助数组来存储。
#include<cstdio>
#include<cstring>
#define Rint register int
using namespace std;
typedef long long LL;
const int N = , mod = ;
int n, m, K, head[N], to[N << ], nxt[N << ], size[N];
inline void add(int a, int b){
static int cnt = ;
to[++ cnt] = b; nxt[cnt] = head[a]; head[a] = cnt;
}
LL dp[N][][], f[][], ans[], S[][];
inline void dfs(int x, int fa){
size[x] = ;
dp[x][][] = ; dp[x][][] = ; ++ ans[];
for(Rint i = head[x];i;i = nxt[i])
if(to[i] != fa){
dfs(to[i], x);
memcpy(f, dp[x], sizeof f);
for(Rint j = ;j <= K && j <= size[to[i]];j ++)
f[j][] = (f[j][] + dp[to[i]][j][] + dp[to[i]][j][]) % mod;
for(Rint j = ;j <= K && j <= size[x];j ++)
for(Rint k = ;k <= K - j && k <= size[to[i]];k ++){
LL S = (dp[to[i]][k][] + dp[to[i]][k][]) % mod;
LL s1 = dp[x][j][] * S % mod, s2 = dp[x][j][] * (S + (k ? dp[to[i]][k - ][] : )) % mod;
f[j + k][] = (f[j + k][] + s1) % mod;
f[j + k][] = (f[j + k][] + s2) % mod;
ans[j + k] = (ans[j + k] + s1 + s2) % mod;
}
memcpy(dp[x], f, sizeof f);
size[x] += size[to[i]];
}
}
int main(){
scanf("%d%d%d", &n, &m, &K);
for(Rint i = ;i < n;i ++){
int a, b;
scanf("%d%d", &a, &b);
add(a, b); add(b, a);
}
dfs(, );
S[][] = ;
for(Rint i = ;i <= K;i ++)
for(Rint j = ;j <= i;j ++)
S[i][j] = (S[i - ][j - ] + S[i - ][j] * j) % mod;
LL fac = , res = ;
for(Rint i = ;i <= K;i ++){
fac = fac * i % mod;
res = (res + fac * S[K][i] % mod * ans[i] % mod) % mod;
}
printf("%lld", res);
}