pekempey's blog

998244853

Sandy the foodie

https://www.codechef.com/problems/KOK100

euler-tour tree。O(n log n) ではあるけど、定数倍が重くて通らなかった。

euler-tour を考えるとき辺で見るか、頂点で見るかどちらかだと思うけど、辺で考えると対称性が良い気がするので辺で実装している。今回の問題のように頂点に値を持たせる場合は、仮想的な何かを差し込んでおいてそれを使うと良い。