Collision [AtCoder Beginner Contest 209 D]

https://atcoder.jp/contests/abc209/tasks/abc209_d

前提知識

• LCA

解説

https://atcoder.jp/contests/abc209/submissions/24156786

この問題はアルゴリズム力が要求される問題。
何が分かれば問題が解けるかという所から考えていく。
なお、想定解法は全然違います。

何が分かれば問題が解けるか

この問題は木上の2点間の距離が分かれば、解くことができる。
距離が偶数であれば頂点上で出会うし、距離が奇数であれば道上で出会う。
まずは、この部分に気付く所が第一段階になる。

木上の2点間の距離

木上の2点間の距離を解く問題はアルゴリズム的な典型問題であるので、それを適用して解いていく。
この部分が本質ではあるのだが、この部分は他方でも多く解説されているので、適当に以下にまとめておく。
意外と要求知識も多くLCAを求める段階もそれほど簡単ではない。
だが、汎用的に使えるのでライブラリを持ってない場合は整備しておくことを勧める。

• 木の適当な頂点を根として決める
  • どこか根を用意する必要がある
• LCAを使って、2頂点の共通祖先を求める
  • ダブリングでLCAを実装する（オススメ）
    • ダブリングによる木の最近共通祖先（LCA：Lowest Common Ancestor）を求めるアルゴリズム | アルゴリズムロジック
    • LCAを理解するにはダブリングをさらに理解する必要がある…
  • HL分解でLCAを実装する（自分の実装はこっち）
    • HL分解・オイラーツアー入門 - ano3のブログ
  • RMQ（RMQが最速と自分のメモには書いてあるけど信用ならんな…）
• 累積和を使って、2頂点の共通祖先への距離を求めることで、2点間の距離を求める
  • 頂点aと頂点bの共通祖先をlca(a,b)とすると、dist(根,a) + dist(根,b) - 2*dist(根,lca(a,b))が頂点ab間の距離

想定解法

2部グラフか…なるほど、賢い…

int N, Q;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> Q;

    HLDecomposition hld;
    hld.init(N);

    rep(i, 0, N - 1) {
        int a, b; cin >> a >> b;
        a--; b--;
        hld.add(a, b);
    }
    hld.build(0);

    rep(i, 0, Q) {
        int c, d; cin >> c >> d;
        c--; d--;

        int len = hld.distance(c, d);

        if (len % 2 == 0) printf("Town\n");
        else printf("Road\n");
    }
}