AtCoder

存在初始为空的点集 \(S\), 进行 \(n\) 次操作, 形如:

\(n \leqslant 2 \times 10^{5}, k, u \leqslant 10^{18}\).

给定一颗 \(n\) 个点的树, 求黑白染色的方案数, 使任意一条路径上的黑点数量不超过 \(2\).

\(2 \leqslant n \leqslant 3 \times 10^{5}, \mathrm{mod} = 998244353\).

引理

证明

考虑枚举右端点 \(R\)，计算对于每个 \(R\) 有多少个左端点 \(L\) 满足条件。

左端点需要满足的条件如下：

转化条件：

时间复杂度 \(\Theta(n)\)。

观察到每个点度数都恰好为 \(2\)，于是连边后构成若干个环。

考虑枚举最大边，分别计算从两个端点出发能走到多少个点。

可以发现并查集能够很好地拟合这个过程，于是将边从小到大加入，每次合并的两个点集即为所求。

时间复杂度 \(\Theta(n \log n)\)。

总时间复杂度 \(\Theta(n^{2})\)。

考虑使用 \(\rm bfs\)。

观察到每一步的代价都是 \(0\) 或 \(1\)，于是建立双端队列。每次迭代取队头，如果走了代价为 \(0\) 的边就将出点加入队首，否则加入队尾。

时间复杂度 \(\Theta(nm)\)。

考虑使用状压 \(\rm DP\)。

考虑记 \(f_{i, u}\) 表示走 \(i\) 步到 \(u\) 的方案数。显然有转移式：

状态数为 \(nk\)，转移的时间复杂度为 \(\Theta(n)\)，于是总时间复杂度为 \(\Theta(n^{2} k).\)

考虑到删除的边数很少，于是将转移方程改写为：