D - Collision（686）

問題

問題文

高橋王国は N 個の街と N−1 本の道路からなり、街には  1 から N の番号がついています。また、i ( 1 ≤ i ≤ N−1 ) 本目の道路は街 ai と街 bi を双方向に結んでおり、どの街からどの街へもいくつかの道路を通ることで移動できます。道路は全て同じ長さです。
Q 個のクエリが与えられます。 i ( 1 ≤ i ≤ Q )番目のクエリでは整数 ci, di が与えられるので、以下の問題を解いてください。
・現在高橋君は街 ci に、青木君は街 di にいる。二人が同時に街を出発し、それぞれ街 di, ci を目指して同じ速さで移動するとき、二人が街で出会うか道路上（両端の街を除く）で出会うかを判定せよ。ただし、二人とも最短経路で移動し、街の中を移動する時間は無視できるものとする。

制約

2 ≤ N ≤ 10^5
1 ≤ Q ≤ 10^5
1 ≤ ai < bi ≤ N ( 1 ≤ i ≤ N−1 )
1 ≤ ci < di ≤ N ( 1 ≤ i ≤ Q )
入力は全て整数
どの街からどの街へもいくつかの道路を通ることで移動できる

考察

まず、前提として、高橋くんと青木くんの距離の差が

偶数：街
奇数：道路

で出会うことになります。ですので、各クエリにおいて二人の距離を求めることによりクエリに答えることができます。しかし、制約をみますと、

2 ≤ N ≤ 10^5
1 ≤ Q ≤ 10^5

ですね。各クエリごとに指定された頂点間の距離を求めるのはちょっと厳しそうです。

効率よくこのクエリを処理するために、問題の性質を考えます。
この問題で大切なのは次の要素です。

・街は N 個
・道は N-1本
・どの街からどの街へもいくつかの道路を通ることで移動可能

この条件を満たすグラフって木構造のグラフしかありません。Pathグラフと言えばいいのか、閉路を持たないグラフと言えばいいのかわかりませんが、とにかく木になります。これとっても大切です。

またさらに言いますと、

道路は全て同じ長さです

とあります。ですので、今回は全ての道の長さを１としておきましょう。頂点０を根とする木のグラフを考えてみます。

このとき注目するのは各頂点の深さです。頂点０からの距離といっても良いです。

各頂点の深さの差を求める

これで、判断が可能です。この計算が２頂点の距離になるわけではありませんが、距離の偶奇を求めるにはこれで十分です。深さの差が偶数であれば、距離の差も偶数になりますし、奇数でも同様なことが言えます。実際に、グラフ上で高橋くんと青木くんを動かしてみるとそうなることが確認できると思います。

このように各頂点の深さがわかっていれば各クエリをO(１)で処理することが可能です。まずは、BFSやDFSなんかで基準からの深さを求めてあげまして、それを使ってクエリを処理すればACがもらえます。

実装しましょう。

実装

 #include <bits/stdc++.h> #define  rep(i,n) for(int i=0;i<n;++i) #define  reps(i,s,n) for(int i=s;i<n;++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
using T = tuple<int, int, int>;


int main()
{
   int n, Q;
   cin >> n >> Q;
   vector<vector<int>> g(n);
   rep(i, n-1)
   {
       int a, b;
       cin >> a >> b;
       --a, --b;
       g[a].emplace_back(b);
       g[b].emplace_back(a);

   }
   vector<int> d(n,-1);
   d[0] = 0;
   queue<P> q;
   q.emplace(0, 1);
   while (!q.empty())
   {
       int e, di;
       tie(e, di) = q.front();
       q.pop();
       for (auto ei : g[e])
       {
           if (d[ei] != -1) continue;
           d[ei] = di;
           q.emplace(ei, di + 1);
       }
   }
   while (Q--)
   {
       int x, y;
       cin >> x >> y;
       --x, --y;
       if (abs(d[y] - d[x]) % 2 == 0)cout << "Town" << endl;
       else cout << "Road" << endl;
   }
   

   return 0;
}

あとがき

木であるかどうかを判断するのが非常に大切な問題でした。問題文には書かれていませんが、考察でも書いた３条件

・N 頂点
・N-1 辺
・連結

のグラフは木になることは覚えておきましょう。「ここテストに出るよ」ってぐらい重要な性質です。この条件を満たす木以外のグラフをどうにか作ることができないか、と試してみると忘れにくいかもしれないですね。