Jinan 2023 B
朴素 dp：\(f_{i, j}\) 代表 \(i\) 为根的子树划分完，\(i\) 所在连通块大小为 \(j\)。转移平凡 \(O(nk)\)。
考虑 \(k\) 很大时复杂度退化成 \(n ^ 2\)。发现 \(k\) 很大时连通块个数很小，只有 \(O(\dfrac{n}{k})\) 级别。因此不妨设 \(f_{i, a, b}\) 表示 \(i\) 为根，子树中有 \(a\) 个大小为 \(k\) 的，\(b\) 个大小为 \(k + 1\) 的，\(sz_i - ak - b(k + 1)\) 个节点在 \(i\) 所在连通块。发现状态总数实际上是 \(O(n \times \dfrac{n}{k})\) 的。
对 \(k\) 进行阈值分治，不难发现当 \(k = \sqrt n\) 是取得最有复杂度，即为 \(O(n ^ {1.5})\)。
using namespace std;
const int N = 100010;
const int mod = 998244353;
vector<int> E[N];
int f[N][1010], T, n, k, sz[N];
unordered_map<int, int> f2[N];
void dfs(int u, int fa) {
sz[u] = 1; f[u][1] = 1;
for (auto v : E[u]) if (v ^ fa) {
dfs(v, u); vector<int> g(min(sz[u] + sz[v], k + 1) + 1);
rep(i, 0, min(sz[u], k + 1))
rep(j, 0, min(sz[v], k + 1 - i))
g[i + j] = (g[i + j] + f[u][i] * f[v][j]) % mod;
rep(i, 0, min(sz[u] + sz[v], k + 1)) f[u][i] = g[i];
g.clear(); g.shrink_to_fit(); sz[u] += sz[v];
} f[u][0] = (f[u][0] + f[u][k]) % mod;
f[u][0] = (f[u][0] + f[u][k + 1]) % mod;
}
void dfs2(int u, int fa) {
f2[u][1] = 1;
for (auto v : E[u]) if (v ^ fa) {
dfs2(v, u); unordered_map<int, int> g;
for (auto [x1, y1] : f2[u]) for (auto [x2, y2] : f2[v]) if (x1 + x2 <= k + 1)
(g[x1 + x2] += y1 * y2 % mod) %= mod; f2[u] = g;
} if (f2[u].find(k) != f2[u].end()) (f2[u][0] += f2[u][k]) %= mod;
if (f2[u].find(k + 1) != f2[u].end()) (f2[u][0] += f2[u][k + 1]) %= mod;
}
signed main() {
scanf("%lld", &T);
while (T -- ) {
scanf("%lld%lld", &n, &k);
rep(i, 1, n) E[i].clear();
rop(i, 1, n) {
int a, b; scanf("%lld%lld", &a, &b);
E[a].push_back(b), E[b].push_back(a);
} if (k <= (int)sqrt(n) * 3) {
rep(i, 1, n) rep(j, 0, k + 1) f[i][j] = 0;
dfs(1, 0); printf("%lld\n", f[1][0]);
} else {
rep(i, 1, n) f2[i].clear();
dfs2(1, 0); printf("%lld\n", f2[1][0]);
}
} return 0;
}
ECFinal 2023 C
第一眼看到这道题的想法：\(f_{i, j}\) 表示 \(x\) 的前 \(i\) 个位置和为 \(j\) 的方案，以及 \(g_{i, j}\) 表示 \(y\) 的前 \(i\) 个位置和为 \(j\) 的方案。这部分可以 \(O(n ^ 2 w)\)。
枚举 \(p, q\)。需要求出 \(\sum \limits_{i \le \min(s_p, s_q)} f_{p, i} \times f_{q, i}\)。这是一个向量点积的形式。发现这个东西是 \(O(n ^ 3 w)\) 的。使用多项式科技可以 \(O(n ^ 2w\log)\)。
考虑更加高级的做法。不妨设 \(f_{i, j, k}\) 表示 \(x\) 中做完了前 \(i\) 个，\(y\) 中做完了前 \(j\) 个，\(s_b - s_a = k\) 的方案数。
若 \(k > 0\) 则转移到 \(f_{i + 1, j}\)，否则转移到 \(f_{i, j + 1}\)。由于第三维大小是介于 \(-w\) 到 \(w\) 之间的，因此复杂度 \(O(n ^ 2 w)\)。
Nanjing 2023 D
一个简单的思路是：设 \(f_{i, j}\) 表示以 \(i\) 为根，叶子节点到根节点路径上黑色节点个数均为 \(j\) 所需要修改的最少点数。这样可以做到 \(O(nm)\)。转移方程是：
\[f_{u, i} \leftarrow \min\{c_{u, 0} + \sum f_{v, i - 1}, c_{u, 1} + \sum f_{v, i}\} \]这个东西可以长链剖分，然后对于轻链的合并做 \((\min, +)\) 卷积即可。可以做到线性。
标签：sz,f2,min,int,auto,记录,mod From： https://www.cnblogs.com/Link-Cut-Y/p/18575187