#ABC209D. [ABC209D] 碰撞(Collision)

    ID: 2777 Type: Default 1000ms 256MiB Tried: 0 Accepted: 0 Difficulty: (None) Uploaded By: Tags>ABC入门算法闯关图论基础与树

[ABC209D] 碰撞(Collision)

题目描述

AtCoder 国由 NN 个城镇和 N1N−1 条道路组成,城镇编号从 11NN。第 ii 条道路 (1iN1)(1≤i≤N−1) 连接城镇 aia_i 和城镇 bib_i,使得可以从任何城镇到达任何其他城镇。所有道路长度相同。

你将收到 QQ 个查询。在第 ii 个查询 (1iQ)(1≤i≤Q) 中,给定整数 cic_idid_i,解决以下问题:

小高现在在城镇 cic_i,小李现在在城镇 did_i。他们将同时离开城镇并以相同的速度开始旅行,小高前往城镇 did_i,小李前往城镇 did_i

确定他们是否会在某个城镇相遇或在某条道路的中途相遇。这里假设他们都沿最短路径行走,通过城镇的时间可以忽略不计。

输入格式

第一行输入点数 NN 和询问次数 QQ

第二行到第 NN 行,第 (i1)(i-1) 行输入两个数 ai,bia_i,b_i,表示第 ii 条边连接的两个点。

从第 (N+1)(N+1) 起的 QQ 行,第 ii 行输入两个数 ci,dic_i,d_i,表示第 ii 次询问的两个点。

输出格式

输出 QQ 行。第 ii(1iQ)(1≤i≤Q) 应包含 "Town",如果小高和小李在第 ii 个查询中将在城镇相遇,或者 "Road",如果他们在该查询中将在道路中途相遇。

输入输出样例 #1

输入 #1

4 1
1 2
2 3
2 4
1 2

输出 #1

Road

输入输出样例 #2

输入 #2

5 2
1 2
2 3
3 4
4 5
1 3
1 5

输出 #2

Town
Town

输入输出样例 #3

输入 #3

9 9
2 3
5 6
4 8
8 9
4 5
3 4
1 9
3 7
7 9
2 5
2 6
4 6
2 4
5 8
7 8
3 6
5 6

输出 #3

Town
Road
Town
Town
Town
Town
Road
Road
Road

说明/提示

样例 1 解释

在第一个也是唯一的查询中,小高和小李分别同时离开城镇 11 和城镇 22,他们将在第 11 条道路的中途相遇,所以我们应该打印 "Road"

样例 2 解释

在第一个查询中,小高和小李分别同时离开城镇 11 和城镇 33,他们将在城镇 22 相遇,所以我们应该打印 "Town"

在第二个查询中,小高和小李分别同时离开城镇 11 和城镇 55,他们将在城镇 33 相遇,所以我们应该打印 "Town"

数据规模与约定

  • 输入的数值均为整数;
  • 2N1052\le N\le 10^51Q1051\le Q \le 10^5
  • 1ai,bi,ci,din1\le a_i,b_i,c_i,d_i\le n,且对于同一个 ii,都有 ai<bia_i\lt b_ici<dic_i\lt d_i
  • 可以从每个城镇到达每个城镇