传统题 文件IO:collision 1000ms 256MiB

碰撞

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

某国由 N 个城镇和 N−1 条道路组成,城镇编号从 1 到 N。第 i 条道路 (1≤i≤N−1) 连接城镇 ai 和城镇 bi ,使得可以从任何城镇到达任何其他城镇。所有道路长度相同。

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

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

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

输入格式

第一行输入点数 N 和询问次数 Q。

第二行到第 N 行,第 (i−1) 行输入两个数 ai,bi ,表示第 i 条边连接的两个点。

从第 (N+1) 起的 Q 行,第 i 行输入两个数 ci,di ,表示第 i 次询问的两个点。

输出格式

输出 Q 行。第 i 行 (1≤i≤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

样例 1 解释

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

样例 2 解释

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

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

数据规模与约定

输入的数值均为整数;

2≤N≤10^5 ,1≤Q≤10^5 ;

1≤ai,bi,ci,di≤n,且对于同一个 i,都有 ai <bi , ci<di 。

可以从每个城镇到达每个城镇

图灵周赛 Round 30(一场)

未参加
状态
已结束
规则
IOI
题目
4
开始于
2025-11-15 21:00
结束于
2025-11-16 1:00
持续时间
4 小时
主持人
参赛人数
16
v>