AT_abc209_d.[ABC209D] Collision
普及-
通过率:0%
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
给出一张 n 点 (n−1) 边的无向图,第 i 条边连接点 ai 和点 bi,长度为 1。
给出 q 个询问。第 i 个询问给出两个点 ci 和 di。请求出两点之间的最短路长度,若为奇数请输出Road,若为偶数请输出Town。保证图联通。
输入格式
第一行输入点数 n 和询问次数 q。
第二行到第 n 行,第 (i−1) 行输入两个数 ai,bi,表示第 i 条边连接的两个点。
从第 (n+1) 起的 q 行,第 i 行输入两个数 ci,di,表示第 i 次询问的两个点。
输入输出样例
输入#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-3-4-5)。1 和 3 之间的最短路长度为 2,1 和 5 之间的最短路长度为 4。它们都是偶数,所以都输出Town。
数据规模与约定
对于 100% 的数据,保证:
- 输入的数值均为整数;
- 2≤n≤105,1≤q≤105;
- 1≤ai,bi,ci,di≤n,且对于同一个 i,都有 ai<bi,ci<di。
输入解题思路,AI测评打分。不知道怎么写?