この問題を解くためには、木構造及びその二部グラフ性について、そして幅優先探索または深さ優先探索についての知識が必要です。これらは競技プログラミングにおいて頻出なので、必要な知識はインターネット上の文献などを参照することができます。

これらの用語を初めて聞いたという方は、本解説を読む前にインターネットなどで検索することをお勧めします。

高橋王国はグラフ理論の用語でいう木構造をなしています。

道路の長さを \(1\) として、街 \(1\) との最短距離が偶数であるような街を赤、そうでない街を青で塗ることにします。

すると、木の二部グラフ性により、赤の街にいた人は次青の街へ、逆に青の街にいた人は次赤の街へ移動するということが分かります。よって高橋君と青木君のスタート地点の色が異なっていれば、二人は必ず同じ街で出会うことはありません。逆に、高橋君と青木君のスタート地点の色が同じであれば、二人は必ず道路で出会うことはありません。
よって初めに各街の色を前計算しておくことで各クエリに \(O(1)\) で答えることができます。

各街の色を求めるには幅優先探索や深さ優先探索を使うと良いです。

類題：https://atcoder.jp/contests/abc126/tasks/abc126_d

#include<bits/stdc++.h>
using namespace std;

int main(){
    int N, Q; cin >> N >> Q;
    vector<vector<int>> G(N);
    for(int i = 0; i < N-1; i++){
        int A, B; cin >> A >> B;
        G[A-1].push_back(B-1);
        G[B-1].push_back(A-1);
    }
    queue<int> que;
    vector<int> dis(N,-1);
    que.push(0);
    dis[0] = 0;
    while(!que.empty()){
        int t = que.front(); que.pop();
        for(int x: G[t]) if(dis[x] == -1) {
            dis[x] = dis[t] + 1;
            que.push(x);
        }
    }
    for(int i = 0; i < Q; i++){
        int A, B;cin >> A >> B;
        if(dis[A-1]%2 == dis[B-1]%2) cout << "Town" << endl;
        if(dis[A-1]%2 != dis[B-1]%2) cout << "Road" << endl;
    }
}

import queue

N,Q=map(int,input().split())
G=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
que=queue.Queue()
color=[-1]*N
color[0]=0
que.put(0)
while not que.empty():
    t=que.get()
    for i in G[t]:
        if color[i] == -1:
            color[i] = 1 - color[t]
            que.put(i)
for i in range(Q):
    a,b=map(int,input().split())
    if color[a-1] == color[b-1]:
        print("Town")
    else:
        print("Road")