Star Tree

子任务 1：直接更新

对每个询问，用 BFS 找到从 $x$ 到 $y$ 的路径，再从 $x$ 开始依次加上 $1,2,\ldots$。时间为 $O(N+NQ)$，空间为 $O(N)$，足以处理 $N,Q\leq2000$。

子任务 2：按编号排列的链

若所有边均为 $\{i,i+1\}$，路径就是整数区间。当 $x<y$ 时，对 $[x,y]$ 中的顶点 $v$ 加上 ；否则对 加上 。分别用两个差分数组维护 的系数和常数项，再求前缀和，即可在 时间、 空间内完成。

完整解法：深度的一次式

以顶点 $1$ 为根，记深度为 $d(v)$，父亲为 $p(v)$。根的深度为零，父亲为虚拟顶点 $0$。对于询问 $(x,y)$，记两点的 LCA 为 ，将路径分成从 到 的部分，以及从 的下一个顶点到 的部分。

第一部分中，顶点 $v$ 增加的值为

$$d(x)-d(v)+1=-d(v)+(d(x)+1).$$

第二部分中为

$$d(x)-d(z)+d(v)-d(z)+1=d(v)+(d(x)-2d(z)+1).$$

因此可以分别增加深度的系数与常数项。只在第一部分包含 $z$，避免重复计算。

祖先路径上的树上差分

若 $w$ 是 $u$ 的祖先，要对从 $u$ 到 $w$ 的闭区间上的顶点增加常数 $c$，可以记录

$$D[u]\mathrel{+}=c,\qquad D[p(w)]\mathrel{-}=c.$$

记录全部操作后，自底向上将子节点的值加到父节点。每个顶点的最终值就是其子树内差分的总和。从 $u$ 出发的贡献会到达 $w$，而在更高处被 $p(w)$ 的反向记录抵消。

使用数组 $A$ 记录深度系数，数组 $B$ 记录常数项。对每个询问，令 $c_1=d(x)+1$，$c_{}$，记录

$$A[x]\mathrel{-}=1,\quad B[x]\mathrel{+}=c_1,$$ $$A[p(z)]\mathrel{+}=1,\quad B[p(z)]\mathrel{-}=c_1,$$ $$A[y]\mathrel{+}=1,\quad B[y]\mathrel{+}=c_2,$$ $$A[z]\mathrel{-}=1,\quad B[z]\mathrel{-}=c_2.$$

第二部分不包含 $z$，所以在 $z$ 而非 $p(z)$ 处抵消。若 $y=z$，这两项立即抵消，正确表示空区间。

处理完全部询问后，按父亲先于孩子的顺序的逆序遍历，将每个顶点的 $A,B$ 加给父亲。虚拟顶点 $0$ 不输出，也不向实际树上传播。顶点 $v$ 的答案为

$$A[v]d(v)+B[v]\pmod{998\,244\,353}.$$

正确性与复杂度

两个区间无重叠地划分原路径，两条一次式均等于从 $x$ 到当前顶点的距离加一。树上差分恰好对各区间内的顶点加入所需系数。由线性性，将全部记录统一累加与逐条直接处理询问完全相同。

用倍增求 LCA，预处理为 $O(N\log N)$，每个询问为 $O(\log N)$，最后累加为 $O(N)$，总时间为 $O((N+Q)\log$，空间为 。当 时不可能有询问，答案为零。合法树的深度可达 ，因此父亲、深度与最后的累加均用非递归方式实现。

独立验证解法

另一份 HLD 实现将路径分解为带方向的连续编号区间。将从 $x$ 一侧得到的区间按原顺序排列，再将 $y$ 一侧的区间逆序接上。维护下一个要增加的数，即可将每个区间的增加值写成编号的系数 $+1$ 或 $-1$ 与常数项，并用普通数组差分处理。它使用区间的实际顺序和长度，而非上述 LCA 深度公式。时间为 $O(N+Q\log N)$，空间为 。

整数范围

单个顶点的最终整数值不超过 $QN\leq2.5\cdot10^{11}$。差分与负的中间值也完全在有符号 64 位整数范围内。不能将差分存为 32 位整数，也不能先做两个 32 位数的乘法再转为 64 位。可以全程使用 64 位累加，仅在输出时取模。

Solution written by GPT6