P12423 【MX-X12-T6】「ALFR Round 5」Coloring Nodes 题解

EasonLiang · 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。