ABC187 E Through Path
ここではあえて解説とは別の自分が本番中にやった複雑な解法を紹介する.
Euler Tour + 遅延セグメント木 + 木上DFSを用いて実装する.
まず根(頂点0)からの各頂点の距離をDFSで前計算しておく.
その後Euler Tourをして区間の形で扱えるようにする.
そして遅延セグメント木を2つもつと解ける.
実装例:
https://atcoder.jp/contests/abc187/submissions/19146734