(PKU+NOI)WC 2025 题解
引用框里写的是赛时想法。
PKUWC 2025
d1t1
通过百万富翁一题的结论不难想到，一定是询问若干个团。询问一个大小为 $a$ 的团可以找到至少 $a-1$ 个坏电池。之后 $n^3$ DP 或者直接推出式子均可通过。（赛时写的 $n^3$）
场切。
d1t2
赛时会了没调完的题。
考虑 $l=1$ 怎么做。
扫描线，注意到对于深度不同的两个点 $p,q$，他们的 $x$ 级祖先必然不同。因此我们对于每个深度 $d$ 维护一棵虚树，查询就是查询每棵虚树对应深度点数之和。使用 bit 维护即可。这样是 1log 的，同时也给出了一个根号 log 的莫队做法。但是后者常数非常大，跑不动 sub3。
题外话：听说 这个莫队做法回滚后可以做到单根号，有人场上用这个过了。
继续分析性质，如果 $l$ 不一定为 $1$，那么我们相当于要去除虚树上“过期”的点。容易想到我们对于每个点，维护其最后一次被覆盖到的时间 $t_i$，修改相当于链赋值，查询相当于查询每棵虚树对应深度 $t_i \ge l$ 的点的数量。修改可以在每条重链上维护颜色段均摊，查询则是带修二维数点的形式。赛时写的 bit 套 pbds 的红黑树，常数很大而且写挂了。由于赛时的树剖疑似挂了笔者并不清楚树套树能否通过本题（有人声称过了但是不清楚他是怎么写的）。一个更快的写法是，将带修二维数点转成三维数点然后跑 CDQ。这样复杂度是 $O(n \log^3 n + m \log^2 n)$，常数中等，可以通过。
d1t3
好题要点赞！
本题有一个非常简洁的线性做法。
一个想法是既然题目要求我们求出每个点最早的获胜时间，而这个东西信息量已经有 $O(n)$ 了那么我们不妨只留下这个看看能不能递推。考虑 sub3，记 $f_i$ 表示起点是第 $i$ 个点时的答案（也就是最早的可获胜的时间），$g_i$ 为第一步允许留在起点时第 $i$ 个点的答案。首先一定有 $f_i = \min\limits_{(i,j) \in E} g_j, g_i \gets f_i$，然后对于 $g$，由于 $b_i=i$ 我们是知道如果第一步要留在 $i$ 所需时刻的，如果 $f_i \le a_i$ 那么第一步留在 $i$ 肯定不优；否则后手会在 $a_i+1$ 时刻从 $i$ 出发，若 $f_i = a_i+1$ 那么先手必败，否则先手必胜，令 $g_i \gets a_i$。
接着考虑 sub4。首先缩点，记 E' 为缩点后形成 DAG 的边集。（一个小细节是 tarjan 求出来的就是反拓扑序，直接用就好了，不需要重新拓扑排序。）修改状态定义，令 $f_i,g_i$ 为第 $i$ 个 SCC 内任取一个起点的上述值，由于 SCC 内答案相同所以是良定义的。
特判连通块内只有一个点的情况，此时与 sub3 转移相同。
否则：
- 一个 SCC 有多个起始时间可选；
- 一个点可以走回自己，故有 $f_i = g_i$。
依然考虑求出 $\min\limits_{(i,j) \in E'} g_j$，记作 $t$。接下来考虑在 SCC 内走的情况。
将 SCC 内所有点的对应时刻写在数轴上，找出第一段连续段 $[st,ed]$（这个 sub 中暴力找的复杂度就是正确的）。如果 $st \ge t$ 那么走到 SCC 内一定不优；否则，考虑 $\min(ed, t)$，不难发现在这个位置先手一定必胜，且在这之前先手的胜负状态是交替的（因为之前二人都不可能走出 SCC），通过奇偶性即可知道第一个先手必胜的时刻是 $st$ 还是 $st+1$。
上述代码稍微修改一下即可获得 75 分，究其原因，在每个点的颜色有多个出现时刻的时候，暴力找连续段的复杂度不被 $|\text{SCC}_i|$ 所控制，总复杂度退化为 $O(n^2)$。
考虑使用数据结构维护。求 $st$ 的复杂度依然正确，但是我们要支持快速找到 $st$ 后第一个未在 SCC 内出现的颜色。考虑从后往前扫描线，每次只保留每个颜色第一次出现的位置，这样每个颜色只出现一次，暴力找复杂度就对了，相当于要支持任意位置删除，push_front 和从头开始按顺序遍历，使用链表维护即可。一个小细节是看上去要持久化，但是注意到找连续段的过程与维护 $f$ 和 $g$ 无关，我们直接在最开始离线一下预处理即可。复杂度 $O(n)$。
d2t1
有趣（？）的交互题。
考虑维护直径的三个端点 $x,y,z$。初始设置为 $1,2,3$。第一轮将 $x$ 替换为
query(p,y,z)最大的 $p$。第二轮替换 $y$，第三轮替换 $z$。这样使用了 $3n - \epsilon$ 次询问，找到了三个点（其中至少包含一条直径）和 $dis(x,y)$。再用 $n$ 次询问可以知道 $dis(x,z)$，即可知道直径。
可以获得 $83$ 分，使用一些随机化技巧可以再高一些。
还能再给力一点吗？
找到 $x,y,z$ 的 $3n - \epsilon$ 次询问已经很紧了，考虑把最后的 $n$ 次询问压缩掉。
首先特判掉 $n \le 6$ 的 corner case。这个阈值是随便取的。
在找到 $z$ 的同时我们其实获得了所有 query(x,y,i) 的值，记作 $f_i$。找到 $f$ 值最小的点 $mn$，通过一次 in 询问即可知道 $mn$ 是否在 $x$ 到 $y$ 的路径上。
- 如果在：
那么 $mn$ 必然在 $x$ 到 $z$ 或者 $y$ 到 $z$ 的路径之一上。再使用一次 in 询问即可知道是哪种情况，这样我们三条链长都知道了。
- 如果不在：
这意味着 $x,y$ 在树上相邻。由于 $n > 6$ 所以树的直径必然不小于 $2$，也就是说 $z$ 一定是直径端点。不难发现此时 $x,y$ 中非直径端点的一者必然在直径上，使用一次 in 询问即可。
d2t2
下称单次消耗代价为 $1$ 的为 A 操作，代价为 $c$ 的为 B 操作。
考虑贪心。不难发现如果我们使用 B 操作时完整地取走了 $k$ 个球，那么一定不劣。进一步，我们发现：
一定存在一组最优解，满足 B 操作形成了若干个连续段，并且只有不在连续段上或者是连续段末尾的位置可能使用操作 A。
通过这个不难设计一个平方 DP。记 $f_i$ 表示将 $[1,i]$ 的盒子内的球全部取完所需代价，两种操作的转移代价都是好算的，拼上 $c=1$ 即可获得 73 分。
进一步考虑什么样的点可能成为连续段末尾。假设 $p$ 是连续段末尾，那么 $a_p$ 可能已经被取走了一些球（不妨记此时为 $a'_p$，并且有 $a'_p + \sum\limits_{i=p+1}^{i+m-1}a_i < k$。
假如我们可以对于每个 $i$ 求出 $i$ 后面第一个可能成为连续段末尾的点 $j$，就可以从后往前 DP。记 $f_i$ 表示 $[i,n]$ 取完的最小代价，分类讨论 $j$ 开始是继续 B 操作还是断开，两种代价都是好算的。
如何快速求 $j$ 呢？注意到上述条件相当于 $(sum_j-sum_{i-1}) \mod k$ 在落在一个区间内，使用颜色段均摊做区间覆盖即可。
d2t3
你觉得这是题吗。
注意到可以贡献到 $[L,R]$ 中的数很少，具体地，考虑倒序撤销操作，那么只有 $[L/y-B,R/y+B]$ 中的数可能出现，其中 $y \in \N^+$。
整除分块找到所有可能产生贡献的区间并去重，发现数的数量可以接受，分解出质因数跑 B 次狄利克雷前缀和，发现过了。
分解质因数的时候要对于不超过 $10^7$ 的数预处理最小质因子。
复杂度不会证，应该也卡不掉。
NOIWC
t1
场切。