4247: Collision

# Collision ### 内存 1024MB ### 时间 2S ## 题目描述 AtCoder国由$N$个城镇和$N-1$条道路组成，城镇编号从$1$到$N$。第$i$条道路$(1≤i≤N-1)$连接城镇$a_i$和城镇$b_i$，使得可以从任何城镇到达任何其他城镇。所有道路长度相同。 你将收到$Q$个查询。在第$i$个查询$(1≤i≤Q)$中，给定整数$c_i$和$d_i$，解决以下问题： 小高现在在城镇$c_i$，小李现在在城镇$d_i$。他们将同时离开城镇并以相同的速度开始旅行，小高前往城镇$d_i$，小李前往城镇$c_i$。确定他们是否会在某个城镇相遇或在某条道路的中途相遇。这里假设他们都沿最短路径行走，通过城镇的时间可以忽略不计。 ## 输入格式 输入从标准输入按以下格式给出： $N$ $Q$ $a_1$ $b_1$ $a_2$ $b_2$ ⋮ $a_{N-1}$ $b_{N-1}$ $c_1$ $d_1$ $c_2$ $d_2$ ⋮ $c_Q$ $d_Q$ ## 输出格式 输出$Q$行。第$i$行$(1 ≤ i ≤ Q)$应包含"`Town`"，如果小高和小李在第$i$个查询中将在城镇相遇，或者"`Road`"，如果他们在该查询中将在道路中途相遇。 ## 输入输出样例 ### 输入样例1 ``` 4 1 1 2 2 3 2 4 1 2 ``` ### 输出样例1 ``` Road ``` ### 输入样例2 ``` 5 2 1 2 2 3 3 4 4 5 1 3 1 5 ``` ### 输出样例2 ``` Town Town ``` ### 输入样例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说明】 在第一个也是唯一的查询中，小高和小李分别同时离开城镇1和城镇2，他们将在第1条道路的中途相遇，所以我们应该打印"`Road`"。 【样例2说明】 在第一个查询中，小高和小李分别同时离开城镇1和城镇3，他们将在城镇2相遇，所以我们应该打印"`Town`"。 在第二个查询中，小高和小李分别同时离开城镇1和城镇5，他们将在城镇3相遇，所以我们应该打印"`Town`"。 【数据范围】 - $2 ≤ N,Q ≤ 10^5$ - $1 ≤ Q ≤ 10^5$ - $1 ≤ a_i < b_i ≤ N (1 ≤ i ≤ N-1)$ - $1 ≤ c_i < d_i ≤ N (1 ≤ i ≤ Q)$ - 所有输入值都是整数。 - 可以从每个城镇到达每个城镇。 ## 题目来源 ABC209D