TouchStone
  Please Login
ログイン 登録
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • 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