概要
動的木を使わなくて良かった．
解法
HL 分解して，heavy path, light edge などの言葉を使います．だいたい次のようにします．
- パスの最後の 2 頂点が与えられたとき，「次の点」を求められるようにしておく．
- 答となるパスを，根方向に上る部分と下る部分に分けてそれぞれ解く．
- heavy path を上るとき．まず「次の点」を求める．次の点が現在地と同じ heavy path 上にある場合には，heavy path 上をいい感じにまとめて上る．そうでなければ light edge に沿って進む．
- heavy path を下るとき：同様．
それぞれの方法について述べます．
まず各頂点の「次の点」を求める方法について．これは各頂点の子の値を priority queue などで管理すればよいです．各 $v$ に対して $v$ を子に持つ頂点は高々 1 つなので，クエリごとに $O(1)$ 回の更新で済みます．親と上位の子高々 2 つを調べることで，「次の点」を計算できます．
次にパスの計算について．heavy path 上の連続する $3$ 点 $a,b,c$ であって，$a$ から $b$ に上ったならば次も必ず $c$ に進むとき，$b$ に立ち寄る必要はありません．立ち寄る必要がある点だけにフラグを立てておいて，「path 上ではじめてフラグの立っている点を調べる」という種類の操作ができればよいです．これは std::set をはじめとしてさまざまな方法で実現可能です．
任意のパスは $O(\log N)$ 個の heavy path または light edge の結合なので，答を得るために $O(\log N)$ 回のフラグの検索や「次の点」の計算ができればよく，$O(\log^2N)$ 時間などで答えを求めることができます．
$A[v]$ が更新された場合，この変更がフラグに影響を及ぼし得るのは $v$ の親および heavy child のみです．よって変更クエリに対して $O(1)$ 回の操作でデータを維持できます．
私が提出したものは厳密には少し上のものと異なります．立ち寄る必要がある「かもしれない」点にフラグを立てておき，更新の際には親と heavy child のフラグをオンにします．そして，パスの探索の際に不要だと判明した点があればフラグをオフにするようにしています．償却計算量 $O((N+Q)\log^2N)$ 時間になります．
