题解：P16844 [GKS 2021 #B] Truck Delivery

· · 题解

Problem

给定一颗 n 个结点的树，根结点为 1。每条边有两个边权 L,A。

数据范围： $n \le 5 \times 10^4,\ q \le 10^5$，同时多测，$T \le 100$。 ## Solution 看到树上路径问题，首先应想到树链剖分，将路径转化为序列问题。边权挂在深度较大的点上作点权，保证边权和点权一一对应。 接下来考虑如何在序列上维护原问题：发现 $L \le W$ 的限制很难处理，于是考虑离线，手动去掉限制。 - 首先，我们将所有询问按 $W$ 升序排序，同时将所有限制 $(L_i,i)$ 也按 $L$ 升序排序； - 接着开一个初始为 $0$ 的线段树，用来维护单点改和区间 $\gcd$。（由于 $0$ 不影响 $\gcd$ 的结果，因此初始值设为 $0$） - 一开始每个点都未被插入线段树。按顺序处理询问时，将当前未插入且满足 $L \le W$ 的所有点插入线段树（此处插入的值是 $A_i$，插入的下标是结点的 $\text{dfn}$），这样一来，线段树上的所有点都满足当前询问，且一定也满足后续的询问，直接在线段树上查询即可获得答案。 单次插入的时间复杂度是 $O(\log{n})$，查询的复杂度也是 $O(\log{n})$，总时间复杂度是 $O(T(n+q)\log{n})$，时限 $5 \text{s}$，可以通过本题。 注意事项：一定要注意数组下标表示结点编号还是 $\text{dfn}$；多测要清空，每个数组都要。 代码有点长，不放了。