Star Tree

Subtask 1: direct updates

For each query, find the path from $x$ to $y$ by BFS and add $1,2,\ldots$ along it starting at $x$. This takes $O(N+NQ)$ time and $O(N)$ space, sufficient for $N,Q\leq2000$.

Subtask 2: the path in label order

When the edges are $\{i,i+1\}$, a path is an integer interval. If $x<y$, add $v-x+1$ at vertex in . Otherwise, add in . Use two range-difference arrays for the coefficient of and the constant term, then take prefix sums. The complexity is time and space.

Full solution: linear functions of depth

Root the tree at vertex $1$. Let $d(v)$ be its depth and $p(v)$ its parent. The root has depth zero and a virtual parent $0$. For query $(x,y)$, let be their LCA. Split the path into the segment from through and the segment after through .

On the first segment, the amount at vertex $v$ is

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

On the second segment, it is

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

Thus each segment receives a constant coefficient of depth and a constant intercept. Include $z$ only in the first segment.

Tree differences for ancestor segments

If $w$ is an ancestor of $u$, adding a constant $c$ to the inclusive segment from $u$ to $w$ can be recorded as

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

After all records, accumulate child values into their parents in bottom-up order. The resulting value at a vertex is the sum of differences in its subtree. The contribution starting at $u$ reaches $w$ and is canceled above it by the opposite record at $p(w)$.

Maintain arrays $A$ for depth coefficients and $B$ for intercepts. For one query, set $c_1=d(x)+1$ and $$, then record

$$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.$$

The second segment excludes $z$, so it is canceled at $z$, not at $p(z)$. If $y=z$, its two records cancel immediately, correctly representing an empty segment.

After processing all queries, traverse vertices in reverse of a parent-before-child order and add each vertex's $A$ and $B$ to its parent. Do not output the virtual vertex $0$ or propagate its value back into the tree. The answer at $v$ is

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

Correctness and complexity

The two segments partition the original path, and each linear expression equals the distance from $x$ plus one. Tree differences add exactly the specified coefficients on each segment. By linearity, combining all records before accumulation produces the same result as performing every query explicitly.

Binary lifting gives $O(N\log N)$ preprocessing, $O(\log N)$ per LCA query, and $O(N)$ final accumulation: $O((N+Q)$ time and space overall. If , there can be no queries and the answer is zero. Trees of depth are valid, so construct parents and depths and perform accumulation iteratively.

Independent verification solution

A separate HLD implementation splits each path into oriented contiguous index intervals. Append the intervals found on the $x$ side in their original order and those on the $y$ side in reverse order. Maintain the next value to add. Each interval then receives an index coefficient of $+1$ or $-1$ and an intercept, handled by ordinary array range differences. This uses the actual order and lengths of intervals rather than the depth formula above. Its complexity is $O(N+Q\log N)$ time and space.

Integer bounds

The final integer value of any vertex is at most $QN\leq2.5\cdot10^{11}$. All differences and negative intermediate values also fit signed 64-bit arithmetic comfortably. Do not store differences in 32-bit integers or multiply two 32-bit values before converting the result. Accumulate in 64-bit integers and take the remainder only when printing if desired.

Solution written by GPT6