Collision

题目描述

高桥王国由 $N$ 个城镇和 $N-1$ 条道路组成，城镇编号为 $1$ 到 $N$。第 $i$ 条道路 $(1 \leq i \leq N-1)$ 连接城镇 $a_i$ 和城镇 $b_i$，使得可以通过若干道路从任意城镇到达任意城镇。所有道路的长度相同。 将给出 $Q$ 个询问。在第 $i$ 个询问 $(1 \leq i \leq Q)$ 中，给定整数 $c_i$ 和 $d_i$，求解以下问题：

高桥现在在城镇 $c_i$，青木现在在城镇 $d_i$。他们同时离开各自的城镇并以相同速度出发，高桥前往城镇 $d_i$，青木前往城镇 $c_i$。确定他们是在某个城镇相遇还是在某条道路的中点相遇。这里，假设他们都沿最短路径行走，且通过城镇所需的时间可以忽略不计。

输入格式

输入从标准输入按如下格式给出： $N$ $Q$ $a_1$ $b_1$ $a_2$ $b_2$ $\hspace{0.6cm}\vdots$ $a_{N-1}$ $b_{N-1}$ $c_1$ $d_1$ $c_2$ $d_2$ $\hspace{0.6cm}\vdots$ $c_Q$ $d_Q$

输出格式

输出 $Q$ 行。 第 $i$ 行 $(1 \leq i \leq Q)$ 应包含 Town，若在第 $i$ 个询问中高桥和青木将在某个城镇相遇；若在该询问中他们会在某条道路的中点相遇，则应包含 Road。

4 1
1 2
2 3
2 4
1 2

Road

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

Town
Town

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

Town
Road
Town
Town
Town
Town
Road
Road
Road

提示

$2 \leq N \leq 10^5$ $1 \leq Q \leq 10^5$ 1 \leq a_i < b_i \leq N\, (1 \leq i \leq N-1) 1 \leq c_i < d_i \leq N\, (1 \leq i \leq Q) 输入中的所有数值均为整数。 可以通过若干道路从任意城镇到达任意城镇。在第一个也是唯一的询问中，高桥和青木分别同时从城镇 $1$ 和城镇 $2$ 出发，他们将在第 $1$ 条道路的中点相遇，所以我们应当输出 Road。
在第一个询问中，高桥和青木分别同时从城镇 $1$ 和城镇 $3$ 出发，他们将在城镇 $2$ 相遇，所以我们应当输出 Town。 在第一个询问中，高桥和青木分别同时从城镇 $1$ 和城镇 $5$ 出发，他们将在城镇 $3$ 相遇，所以我们应当输出 Town。

标签: AtCoder|abc209D

来源

AtCoder|abc209D