Official
E - Through Path Editorial by tatyam
各クエリは、「辺 \(e\) で木を切断した時の連結成分のどちらかに \(x\) を足す」という形になっています。
適当に根を取り、根付き木として考えます。
すると、クエリの内容は、「ある頂点の子孫に \(x\) を足す」または「ある頂点の子孫でない頂点に \(x\) を足す」に言い換えることができます。
「ある頂点の子孫でない頂点に \(x\) を足す」は、「根の子孫に \(x\) を足す」と「ある頂点の子孫に \(-x\) を足す」に分けることができるので、全てのクエリを「ある頂点の子孫に \(x\) を足す」の形に帰着することができます。
これは、いもす法 のように最後に子孫に向かって累積和をとることで、 \(O(N+Q)\) で処理することができます。
また、各クエリで辺 \(e\) 以外では \(c_{a_i}-c_{b_i}\) の値が変わらないことに注目し、 \(c_1\) と \(c_{a_i}-c_{b_i}\) の値を管理しても同様に解くことができます。
回答例 (C++) : https://atcoder.jp/contests/abc187/submissions/19103187
回答例 (Python) : https://atcoder.jp/contests/abc187/submissions/19103203
posted:
last update: