AtCoder Beginner Contest 209 D - Collision【Python】
https://atcoder.jp/contests/abc209/tasks/abc209_d
AtCoder ProblemsのRecommendationでDifficulty: 686、Solve Probability:
37%でした。
幅優先探索で街0から各街への距離を求め、その値がクエリの2つの街それぞれ偶数同士か奇数同士の場合はTown、それ以外の場合はRoadになる事に気づいたためとくことができました。
from collections import deque N, Q = map(int, input().split()) G = [] for _ in range(N): G.append([]) for i in range(N-1): a, b= map(int, input().split()) a -= 1 b -= 1 G[a].append(b) G[b].append(a) dist = [-1] * N que = deque() que.append(0) dist[0] = 0 while len(que) > 0: i = que.popleft() for i2 in G[i]: if dist[i2] == -1: dist[i2] = dist[i] + 1 que.append(i2) for i in range(Q): c, d = map(int, input().split()) if (dist[c-1] % 2 == 0 and dist[d-1] % 2 == 0) or (dist[c-1] % 2 != 0 and dist[d-1] % 2 != 0): print('Town') else: print('Road')