自动搬运

查看原文

来自洛谷，原作者为

	EasonLiang **

搬运于2025-08-24 23:15:29，当前版本为作者最后更新于2024-11-08 20:05:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

声明：本题的某些部分分算法略微卡常，但保证出题人对所有部分分算法的代码实现，在对应子任务中的运行时间均在时间限制的一半以内。

感谢 fjy666 佬的验题！
感谢 Leo_SZ、sunrise1024 帮忙检验了一些部分分。
感谢 NanXl07 实现了暴力程序，并帮我对拍。

算法一

我会暴力！

对于每次询问，枚举 $2^n$ 种染色方案并判断是否满足要求。
时间复杂度 $O(2^nq\operatorname{poly}(n))$，期望得分 0~5pts。

算法二

我会预处理！

对于 $2^n$ 种染色方案中的每一种，记录下 $u$ 到 $v$ 的路径上是否有黑色结点，可以预处理出所有答案，询问时直接回答即可。
时间复杂度 $O(2^n\operatorname{poly}(n)+q)$，期望得分 0~10pts。

接下来的期望得分取决于你是否会写 $w_u < 0$ 的树形 DP。

算法三

我会 DP！

对于每次询问，以 $u$ 为根进行树形 DP。
时间复杂度 $O(nq)$，期望得分 15~20pts。

算法四

我会数点！

将询问离线，对于每个询问到的 $u$，以 $u$ 为根进行树形 DP，并做二维数点。
时间复杂度 $O(kn \log n + q \log n)$，其中 $k$ 为询问到的不同 $u$ 的数量，结合算法三数据点分治后期望得分 25~45pts。

算法五

我会离散化！

注意到算法四的瓶颈在于，对于固定的 $u$，对答案造成贡献的区间数量是 $O(n)$ 的。
考虑对于同一个 $u$ 的询问（假设有 $q_u$ 个），将询问的区间 $[l, r]$ 离散化。
可以证明$^{\dagger}$离散化后，对答案造成贡献的不同区间 $[l, r]$ 的数量只有 $O(q_u)$ 个。
因此，我们可以在 $O(n + q_u \log n)$ 的时间内回答所有根为 $u$ 的询问。
总时间复杂度 $O(kn + q \log n)$，其中 $k$ 为询问到的不同 $u$ 的数量，期望得分 35~65pts。

算法六

我会换根！

考虑换根 DP，不难发现换根后改变的贡献区间数量是 $O(1)$ 的，将贡献离线下来三维数点即可。
总时间复杂度 $O((n+q) \log^2 (n+q))$，期望得分 50~100pts。

$^{\dagger}$证明：$q_u$ 个区间离散化后构成 $O(q_u)$ 个极小区间，将每一个极小区间内的叶结点合并看作一个结点，则这些结点构成的虚树上的所有结点所代表区间，即为所有对答案造成贡献的区间，共 $O(q_u)$ 个。