競プロでグラフの問題を解く時に考えてみること

• 頂点v-u間への操作を考える時、グラフを木にできるなら根rを定めて、v-r,u-rに分けて考えてみる
  • v-uのLCAをpとして、v-uへの操作はv-p,u-pに分けることができる。p-rへの操作を二回しているとみなしてv-r,u-rに分けてみる。「二回操作すると戻る」タイプの場合はp-rへの操作がなかったとみなせるので、v-uへの操作をv-r,u-rへの操作と同一視できる
  • https://atcoder.jp/contests/agc014/tasks/agc014_b