k = 1
设 (S(c) = {c_xmid xin S })， 那么答案就是：
[sum_c|S(c)| = sum_c sum_{i=1}^m[i in S(c)]
]
交换求和符号：
[sum_{i=1}^msum_c [iin S(c)]
]
这个意义就是枚举颜色 i， 然后求有多少种染色方案， 使得 i 在 (S(c)) 中， 设为 G(i)。
然后显然每种颜色是等价的， 那么 G(1) = G(2) = ... = G(m)。
所以只需要求 G(1)， 取个补变成求有几种染色方案使得 1 不在 S(c) 中。
这个比较好算。
标算
相当于求 (sum_c|S(c)|^k)。
根据斯特林展开公式：
[color{teal}{x^k = sum_{i=0}^k {krace i}x^{underline i} = sum_{i=0}^k {krace i}inom xi i!}
]
代入得到：
[color{orange}{sum_c} sum_{i=0}^k{krace i}color{orange}{inom {|S(c)|}i}i!\
sum_{i=0}^k{krace i}i! color{orange}{sum_cinom {|S(c)|}i}
]
剩下的就是求 (g(i) = sum_c inom{|S(c)|}i)， 等价于：枚举所有大小为 i 的颜色集合 t， 并算出有多少 c 满足 (t subseteq S(c))。
令 h(i) 为：对于某个大小为 i 的颜色集合 T， 有几个 c 满足 (t subseteq S(c))。
那么 (g(i) = inom mi h(i))。
对于 (h(i))， 考虑用容斥原理去算， 每次枚举有 j 个 T 中的颜色不在 S(c) 中， 令 dp(j) 表示对于一个大小为 j 的颜色集合 Ban， 有几个 c 满足 (Bancap S(c) = varnothing)， 有：
[h(i) = sum_{j=0}^i (-1)^jinom ijdp(j)
]
对于 dp(j)， 可以直接树形 dp。
那么算法的流程就是：
对于 0...k，预处理出 dp(j)。
然后计算即可。
总复杂度 (O(nk+k^2))。
#include <bits/stdc++.h>
typedef long long LL;
using namespace std;
const int N = 1e5 + 23, K = 93, mo = 998244353;
int n, m, k, _S_, S[N];
bool vis[N];
LL c[K][K], s[K][K];
int ecnt, hd[N], nt[N*2+1], vr[N*2+1];
void ad (int x, int y) { nt[++ ecnt] = hd[x], hd[x] = ecnt, vr[ecnt] = y; }
LL f[N][2], dp[K];
void dfs (int x, int F, int j) {
f[x][0] = 1ll, f[x][1] = vis[x] ? 0ll : 1ll;
for (int i = hd[x]; i; i = nt[i]) {
int y = vr[i];
if (y == F) continue;
dfs (y, x, j);
f[x][0] *= ((LL)(m - j - 1) * f[y][0] % mo + (LL)j * f[y][1] % mo) % mo, f[x][0] %= mo;
f[x][1] *= ((LL)(m - j) * f[y][0] % mo + (LL)(j - 1) * f[y][1] % mo) % mo, f[x][1] %= mo;
}
}
int main()
{
scanf ("%d%d%d%d", & n, & m, & k, & _S_);
for (int i = 1; i <= _S_; ++ i) scanf ("%d", & S[i]), vis[S[i]] = true;
for (int i = 1, x, y; i < n; ++ i) scanf("%d%d", & x, & y), ad (x, y), ad (y, x);
c[0][0] = s[0][0] = 1ll;
for (int i = 1; i <= k; ++ i) {
c[i][0] = 1ll;
for (int j = 1; j <= i; ++ j) {
c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mo;
s[i][j] = (s[i - 1][j] * (LL)j + s[i - 1][j - 1] ) % mo;
}
}
for (int i = 0; i <= k; ++ i)
dfs (1, 0, i), dp[i] = ((LL)(m - i) * f[1][0] % mo + (LL)i * f[1][1] % mo) % mo;
LL ans = 0ll, faci = 1ll;
for (int i = 0; i <= k; ++ i) {
LL now = 0ll;
for (int j = 0; j <= i; ++ j)
now = (now + (j&1 ? -1ll : 1ll) * c[i][j] * dp[j] % mo) % mo;
ans += now * faci % mo * s[k][i] % mo;
ans %= mo;
faci = faci * (LL)(m - i) % mo;
}
cout << (ans % mo + mo) % mo;
return 0;
}