题解

思路

一条只含 $-1$ 和 $1$ 的序列，其所有连续子段和会覆盖从最小子段和到最大子段和之间的每个整数。因为沿着端点移动时，子段和每次只改变一，所以不可能跨过中间整数。空子段使 $0$ 也包含在范围中。

因此对一条查询路径，只需求出最小连续子段和 $mn$ 与最大连续子段和 $mx$，答案就是 $mn\le k\le mx$。

做法

子任务 1：枚举路径的全部子段

沿父指针找到最近公共祖先并还原 $u$ 到 $v$ 的点权序列，再枚举全部连续子段，直接检查是否存在和为 $k$ 的子段。复杂度为每次询问 $O(n^2)$。

子任务 2：还原路径后做线性扫描

仍然显式还原路径，但用 Kadane 动态规划在线性时间求最小和最大连续子段和。每次询问复杂度为 $O(n)$。

子任务 3：倍增维护可合并信息

对一段有方向的点权序列维护七个量：

• 总和 sum；
• 最小、最大前缀和；
• 最小、最大后缀和；
• 最小、最大连续子段和。

所有前后缀和子段都允许为空。设两段依次为 $A,B$，则合并时

最小值同理取最小。反转一段时只需交换前缀与后缀信息。

树只会增加叶子，所以新点加入时可以立即建立祖先倍增表，并让每一级同时保存“从该点向上”的序列信息。查询时先求最近公共祖先，把 $u$ 向上的部分、公共祖先以及 $v$ 向上的部分反转后依次合并，即可得到整条有向路径的信息。

复杂度

三个层级每次询问的复杂度分别为 $O(n^2)$、$O(n)$ 和 $O(\log n)$。满分算法总时间复杂度为 $O(n\log n)$，空间复杂度为 $O(n\log n)$。