题解

思路

因为简单版的询问总从根节点 $1$ 出发，所以每次询问只涉及一条根到节点的路径。关键是维护这条路径上连续子段和的最小值与最大值。

做法

下面先给出两个部分分算法，再推导可随加点操作在线更新的满分状态。

子任务 1：枚举所有连续段

保存每个节点的父亲和权值。询问节点 $v$ 时沿父亲指针还原根到 $v$ 的权值序列，枚举连续段的左右端点并检查其和是否为 $k$；同时单独考虑和为 $0$ 的空段。

若路径长度为 $m$，单次询问需要 $O(m^2)$ 时间。在 $n$ 很小时可以通过。

子任务 2：每次询问重新扫描路径

仍然在询问时还原根到 $v$ 的路径，但不再枚举左右端点。用 Kadane 算法分别求该序列的最小连续子段和 minimum 与最大连续子段和 maximum，空段使区间至少包含 $0$。查询只需判断

$$\texttt{minimum}\le k\le\texttt{maximum}.$$

单次询问为 $O(m)$，在第二层的规模与总事件数限制下可通过。

满分做法：加点时维护状态

对每个节点 $v$ 维护四个量：

• end_min[v]：根到 $v$ 的路径中，以 $v$ 结尾的非空连续段最小和；
• end_max[v]：以 $v$ 结尾的非空连续段最大和；
• path_min[v]：整条根路径上的连续段最小和，允许空段；
• path_max[v]：整条根路径上的连续段最大和，允许空段。

根节点的状态为

$$\texttt{end\_min}= exttt{end\_max}=1,\qquad \texttt{path\_min}=0,\quad \texttt{path\_max}=1.$$

若在父节点 $p$ 下加入权值为 $x$ 的新节点 $v$，则

$$\begin{aligned} \texttt{end\_min}[v]&=\min(x,\texttt{end\_min}[p]+x),\\ \texttt{end\_max}[v]&=\max(x,\texttt{end\_max}[p]+x),\\ \texttt{path\_min}[v]&=\min(\texttt{path\_min}[p],\texttt{end\_min}[v]),\\ \texttt{path\_max}[v]&=\max(\texttt{path\_max}[p],\texttt{end\_max}[v]). \end{aligned}$$

每次加点和询问都只需常数时间。

正确性证明

引理 1

上述转移正确维护了根到每个节点路径上的最小、最大连续子段和。

对新节点 $v$，以 $v$ 结尾的非空连续段要么只含 $v$，要么由以父节点 $p$ 结尾的连续段再接上 $x$，因此前两条转移正确。整条新路径上的最优连续段要么完全位于根到 $p$ 的旧路径中，要么以 $v$ 结尾，因此后两条转移正确。根的初始化也显然成立，故由归纳法得证。

引理 2

对于仅含 $-1$ 和 $1$ 的序列，其连续子段和能取到从最小连续子段和到最大连续子段和之间的每个整数；空段还保证能取到 $0$。

考虑一个取得最大和 $M$ 的连续段。从该段左端开始逐项累加，累加值每次只变化 $1$，由 $0$ 到达 $M$ 的过程中必经过 $0,1,\ldots,M$。对取得最小和的连续段同理，可经过所有从最小值到 $0$ 的整数。因此整个闭区间内的整数均可取得。

定理

算法对每次询问给出的答案正确。

由引理 1，path_min[v] 与 path_max[v] 是询问路径上的真实极值；由引理 2，目标 $k$ 可由某个连续段取得，当且仅当它位于这两个极值之间。因此算法的区间判断与题意完全等价。

复杂度

每个事件只进行常数次运算：

• 时间复杂度：$O(\sum n)$；
• 空间复杂度：$O(\max n)$。