P2260【左偏树】猴子大王 | |
|
问题描述
在一个森林里住着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