TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P2260
  • 题目
  • P2260【左偏树】猴子大王
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    在一个森林里住着N(N<=100000)只猴子。在一开始,他们是互不认识的。但是随着时间的推移,猴子们少不了争斗,但那只会发生在互不认识(认识具有传递性)的两只猴子之间。争斗时,两只猴子都会请出他认识的猴子里最强壮的一只(有可能是他自己)进行争斗。争斗后,这两只猴子就互相认识。

    每个猴子有一个强壮值,但是被请出来的那两只猴子进行争斗后,他们的强壮值都会减半(例如10会减为5,5会减为2)。

    现给出每个猴子的初始强壮值,给出M次争斗,如果争斗的两只猴子不认识,那么输出争斗后两只猴子的认识的猴子里最强壮的猴子的强壮值,否则输出 -1。

    输入格式

    第一行, 一个整数N,表示猴子的数量
    接下来N行,表示猴子的强壮值(<=32767)
    接下来一行,一个整数M(M<=100,000)表示与M次争斗。
    接下来M行,每行两个整数X和Y,表示在编号X和编号Y的猴子间发生了争斗。

    输出格式

    共M行,每行表示一次争斗的结果。如果争斗的两只猴子不认识,那么输出争斗后两只猴子的认识的猴子里最强壮的猴子的强壮值,否则输出 -1。

    样例输入

    5
    20
    16
    10
    10
    4
    5
    2 3
    3 4
    3 5
    4 5
    1 5

    样例输出

    8
    5
    5
    -1
    10


    来源  hdu1512