P14454 [ICPC 2025 Xi'an R] Heart of Darkness

对于一棵树 $T$，定义 $v(T)$ 为将 $T$ 的顶点染成黑色和白色的方案数，且需满足以下条件： - 对于树中任意两个黑色顶点 $u, v$，从 $u$ 到 $v$ 的简单路径上的所有顶点都必须为黑色； - 至少有 $k$ 条无向边 $(u, v)$ 满足 $u$ 和 $v$ 的颜色不同。 对于所有有 $n$ 个标号顶点的无根树 $T$，计算 $\sum v(T)$ 的值，并将结果对 $998244353$ 取模。

输入共一行，包含两个正整数 $n, k$（$1 \leq n \leq 10^7$，$1 \leq k \leq 5000$）。

输出一个整数，表示答案。

在第一个测试用例中，只有 $3$ 种不同的树 $T$，它们都是链形结构，因此每棵树的 $v(T)$ 相同。设 $0$ 表示黑色，$1$ 表示白色，则共有 $5$ 种满足条件的染色方案： $$(0,0,1),\ (1,0,0),\ (1,1,0),\ (0,1,1),\ (1,0,1)。$$ 其中，方案 $(1,1,1)$ 与 $(0,0,0)$ 不满足第二个条件（即没有至少 $k=1$ 条黑白相邻的边），而方案 $(0,1,0)$ 不满足第一个条件（两个黑色顶点之间的路径上存在白色顶点）。 因此，最终答案为 $3 \times 5 = 15$。 翻译由 ChatGPT-5 完成