D - Collision Editorial by en_translator
If you heard such terms for the first time, we recommend you to search on the Internet before reading this Editorial.
Assuming each road has length \(1\), let us paint red those town whose shortest distance to Town \(i\) is even; otherwise, let us paint them blue. Then, due to the bipartiteness of trees, we can see that if a person is currently at a red town, then he next goes to blue town; conversely, a person who is now at a blue town will always move to a red town. Therefore, if the colors of the vertices where Takahashi and Aoki were initially were are different, then they never meet at the same town; On the other hand, if those colors are same, they never meet at a road. To find the colors of the towns, we can use BFS or DFS. Similar problem:https://atcoder.jp/contests/abc126/tasks/abc126_d
Prerequisites
Editorial
Therefore, after we precalculate the color of each town, we can answer each query in an \(O(1)\) time.Sample code (C++)
#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;
}
}
Sample code (Python)
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")
posted:
last update: