AT_abc209_d.[ABC209D] Collision

普及-

通过率:0%

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

给出一张 nn 点 (n−1)(n-1) 边的无向图,第 ii 条边连接点 aia_i 和点 bib_i,长度为 11。

给出 qq 个询问。第 ii 个询问给出两个点 cic_i 和 did_i。请求出两点之间的最短路长度,若为奇数请输出Road,若为偶数请输出Town。保证图联通。

输入格式

第一行输入点数 nn 和询问次数 qq。

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

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

输入输出样例

  • 输入#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)。11 和 33 之间的最短路长度为 22,11 和 55 之间的最短路长度为 44。它们都是偶数,所以都输出Town。

数据规模与约定

对于 100%100\% 的数据,保证:

  • 输入的数值均为整数;
  • 2≤n≤1052\le n\le 10^5,1≤q≤1051\le q \le 10^5;
  • 1≤ai,bi,ci,di≤n1\le a_i,b_i,c_i,d_i\le n,且对于同一个 ii,都有 ai<bia_i\lt b_i,ci<dic_i\lt d_i。

输入解题思路,AI测评打分。不知道怎么写?

首页