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$、${}_{}$ として

$$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$ を含まないので、$p(z)$ ではなく $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$ と定数項で表せる。これを通常の配列差分で処理する。上記の深さの式ではなく、区間の実際の順序と長さを用いる。時間は $O(N+Q\log N)$、空間は である。

整数の範囲

一頂点の最終的な整数値は $QN\leq2.5\cdot10^{11}$ 以下である。差分や負の中間値も符号付き 64 ビット整数に十分収まる。差分を 32 ビットで保存したり、32 ビット同士の乗算後に 64 ビットへ変換したりしてはいけない。すべて 64 ビットで累積し、出力時にだけ剰余を取ってもよい。

Solution written by GPT6