Subtask 0

记前缀和 $s_i=\sum_{j=1}^{i}v_i$。

观察发现可以选定一些点，将所有热量供给给它们，不管其他点。

需要养活这些点，就要在第一个 $s_p<0$ 的时刻点 $p$ 给它们 $-\min_{j=1}^{t}\{s_j\}$ 的热量（每个时刻可以传递无限热量，最优情况就是一次传递所有需要的热量）。

那么定义根节点深度为 $0$，$siz_i$ 为深度 $\leq i$ 的点数，一种方案的答案即为 $\min\{-k/\min_{j=1}^{t}\{s_j\},siz_p\}$（其中 $p$ 为第一个 $s_p<0$ 的时刻）。

暴力枚举 $\{v_n\}$ 即可。时间复杂度 $O((2m+1)^t)$，期望得分 $20$。

Subtask 2

考虑把它变成式子的形式。

先做一些预处理：

• $f_{i,j}$ 表示长度为 $i$ 的，所有数 $\in[-m,m]$，任意前缀和非负，所有数和为 $j$ 的序列数。

• $g_{i,j}$ 表示长度为 $i$ 的，所有数 $\in[-m,m]$，任意前缀和为正，所有数和为 $j$ 的序列数。

• $pre_{i,j}=\sum_{k=0}^{j}f_{i,k}$。

• $s_{a,v}=\sum_{b=a+1}^{t}g_{b-a,v}\times pre_{t-b,tm}$。

记前缀和 $s_i=\sum_{j=1}^{i}v_i$。

枚举 $a$ 为前缀和中第一个负数的位置，$b$ 为前缀和中全局最小的位置，$c$ 为 $s_a$，$d$ 为 $s_b$。

• 为了避免算重，多个最小值在第一个最小值处算贡献。

• 对于 $a=b$ 和前缀和不存在负数的情况要特判算贡献。

则答案为：

$$ \begin{aligned} n\times\left(\sum_{i=0}^{tm}f_{t,i}\right)+\sum_{a=1}^{t}\sum_{c=-m}^{-1}\left(\sum_{i=0}^{c+m}f_{a-1,i}\right)\times\left(\min\{-k/c,siz_a\}\times \left(\sum_{i=0}^{tm}f_{t-a,i}\right)+\sum_{b=a+1}^{t}\sum_{d=-tm}^{c-1}\min\{-k/d,siz_a\}\times g_{b-a,c-d}\times\left(\sum_{i=0}^{tm}f_{t-b,i}\right)\right)\\ =n\times pre_{t,tm}+\sum_{a=1}^{t}\sum_{c=-m}^{-1}pre_{a-1,c+m}\times\left(\min\{-k/c,siz_a\}\times pre_{t-a,tm}+\sum_{d=-tm}^{c-1}\min\{-k/d,siz_a\}\times s_{a,c-d}\right) \end{aligned} $$

直接暴力算就能做到 $O(t^2m^2)$，期望得分 $50$。

Subtask 4

然后是优化这个式子，出题人只会一些很笨的优化。（这是题解原文，不是我辱骂 TA！！！）

• 考虑贡献中的 $\min\{-k/d,siz_a\}$，可以除法分块，预处理 $\{s_{a}\}$ 的前缀和即可做到 $O(tm\sqrt{k})$。

• 然后是预处理 $s_{a,v}=\sum_{b=a+1}^{n}g_{b-a,v}\times pre_{n-b,nm}=\sum_{b=1}^{n-a}g_{b,v}\times pre_{n-a-b,nm}$，这是多项式乘法的形式，可以 NTT 做到 $O(t^2m\log t)$。

• 预处理 $f,g$ 的话，可以前缀和优化做到 $O(t^2m)$。

时间复杂度 $O(tm(t\log t+\sqrt{k}))$，开了 O2 之后 std 最慢点 0.85s。

std：

#include <bits/stdc++.h>
#define REP(i, l, r) for (int i = (l); i <= (r); ++ i)
#define DEP(i, r, l) for (int i = (r); i >= (l); -- i)
#define fi first
#define se second
using namespace std;
namespace Milkcat {
    typedef long long LL;
    typedef pair<LL, LL> pii;
    const int N = 505, M = 2.5e4 + 5, K = 2e5 + 5, mod = 998244353, _G = 3;
	int n, m, t, k, st, inv, u, v, ans, tot;
	int w[M], wi[M], A[M], B[M], val[M], siz[K], f[N][M], g[N][M], pre[N][M], pre2[N][M], ps[N][M];
    vector<int> G[K]; pii Ran[M];
    void prework(int u, int fa, int dep) {
    	siz[dep] ++;
    	for (int v : G[u])
    		if (v != fa) prework(v, u, dep + 1);
	}
	inline int mul(int x, int y) { return 1LL * x * y % mod; }
	inline int qpow(int b, int k) { int r = 1; for (; k; b = mul(b, b), k >>= 1) if (k & 1) r = mul(r, b); return r; }
	inline int dil(int x) { return x >> 31 ? x + mod : x; }
	inline int qmod(int x) { return (x < 0 ? x + mod : (x >= mod ? x - mod : x)); }
	inline void Add(int& x, int y) { x = (x + y) % mod; }
    int main() {
		cin >> t >> m >> n >> k;
		REP(i, 2, t)
			cin >> u >> v, G[u].push_back(v), G[v].push_back(u);
		prework(1, 0, 0);
        REP(i, 1, n) siz[i] += siz[i - 1];
		f[0][0] = 1;
		REP(i, 1, m) g[1][i] = 1;
		REP(i, 0, n * m) pre[0][i] = 1;
		REP(i, 1, n) {
			REP(j, 0, n * m) {
				f[i][j] = dil(pre[i - 1][min(j + m, n * m)] - (j > m ? pre[i - 1][j - m - 1] : 0));
				if (i > 1) g[i][j] = dil(pre2[i - 1][min(j + m, n * m)] - pre2[i - 1][max(j - m, 1) - 1]);
				pre[i][j] = (j > 0 ? qmod(pre[i][j - 1] + f[i][j]) : f[i][j]);
				pre2[i][j] = (j > 0 ? qmod(pre2[i][j - 1] + g[i][j]) : g[i][j]);
			}
		}
		
		st = 1 << (__lg(n * 2 - 1) + 1); inv = mod - (mod - 1) / st;
		w[0] = wi[0] = 1;
		for (int i = 1; i < st; i <<= 1)
			w[i] = qpow(_G, ((mod - 1) >> 2) / i), wi[i] = qpow(_G, mod - 1 - ((mod - 1) >> 2) / i);
		REP(i, 1, st - 1) w[i] = mul(w[i & (i - 1)], w[i & -i]), wi[i] = mul(wi[i & (i - 1)], wi[i & -i]);
		auto NTT = [&](int* a, int n) {
	    	for (int l = n >> 1, r = n; l; l >>= 1, r >>= 1)
		        for (int j = 0, o = 0; j != n; j += r, ++ o)
		            for (int k = j, x, y; k != j + l; ++ k)
		            	x = dil(a[k] - mod), y = mul(a[k + l], w[o]), a[k] = x + y, a[k + l] = x - y + mod;
		};
		auto DNTT = [&](int* a, int n) {
		    for (int l = 1, r = 2; l < n; l <<= 1, r <<= 1)
		        for (int j = 0, o = 0; j != n; j += r, ++ o)
		            for (int k = j, x, y; k != j + l; ++ k)
		            	x = a[k], y = mod - a[k + l], a[k] = dil(x - y), a[k + l] = mul(x + y, wi[o]);
		};
		
		REP(i, 0, st - 1) B[i] = (i < n ? pre[i][n * m] : 0);
		NTT(B, st);
		REP(v, 1, n * m) {
			REP(i, 0, st - 1) A[i] = (i < n ? g[i][v] : 0);
			NTT(A, st);
			REP(i, 0, st - 1) A[i] = mul(A[i], B[i]);
			DNTT(A, st);
			REP(a, 1, n) ps[a][v] = qmod(ps[a][v - 1] + mul(A[n - a], inv));
		}
		
		for (int l = 1, r; l <= min(n * m, k); l = r + 1)
			r = min(k / (k / l), n * m), Ran[++ tot] = pii(l, r), val[tot] = k / l;
		cerr << "Block cnt:" << tot << '\n';
		
		REP(a, 1, n) REP(c, -m, -1)
			Add(ans, mul(pre[a - 1][c + m], mul(pre[n - a][n * m], min(-k / c, siz[a]))));
		REP(c, -m, -1) REP(i, 1, tot) {
			int l = Ran[i].fi, r = Ran[i].se, L = max(l, 1 - c);
			if (r < L) continue;
			REP(a, 1, n) 
				Add(ans, mul(pre[a - 1][c + m], mul(min(val[i], siz[a]), dil(ps[a][c + r] - ps[a][c + L - 1]))));
		}
		Add(ans, mul(pre[n][n * m], t));
		cout << ans << '\n';
        return 0;
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T = 1;
    while (T --) Milkcat::main();
    return 0;
}