TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  训练指南  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P1745
  • 题目
  • P1745【USACO 2011 March Silver】聚会地点
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    Bessie和Jon每天都要去他们所居住的小镇的某些地方游玩。有趣的是,他们居住的小镇是一个树的结构,也就意味是,小镇的每个地方之间有且仅有一条通路(不是指一条边,而是指一条通路),每个地方都会有且仅有一个父亲地点(除了小镇的城镇中心,它没有祖先)。
    小镇共有N个地点(1 <= N <= 1,000),编号1~N。点1是镇的中心。
    Bessie和Jon决定每天都要在游玩后见面,他们见面的地点总是在他们游玩的两个地方之间的那条通路中,离城镇中心最近的地方,下面给出他们的旅行日程,你需要帮他们每天的见面地点。
    你可以理解为城镇中心就是成为在这个树结构上的根。

    以下为他们某次见面的安排:

    输入格式

    第1行:两个数N,M代表一共有N个地方,B和J已经进行了M次见面
    第2..N-1行,每行一个数X,代表第i个地点的父亲为X
    再接下来M行,每行两个数,分别代表B和J当天准备去游玩的地方

    输出格式

    一共M行,每行一个数代表B和J当天见面的地方。

    样例输入

    9 6
    1
    1
    2
    8
    1
    8
    6
    6
    2 7
    4 2
    3 3
    4 1
    7 5
    9 5

    样例输出

    1
    2
    3
    1
    8
    6

    提示

    【数据规模】
    1 ≤ N ≤ 1000
    1 ≤ M ≤ 1000