# HDU – 1512 Monkey King 【可並堆 思維】

AC Code

``````const int maxn = 1e5   5;
int root[maxn];
struct Ltree {
int ls[maxn], rs[maxn];
ll val[maxn];
void cc() {
Fill(ls, 0); Fill(rs, 0);
}
int Un(int x, int y){
if (!x || !y) return x y;
if (val[x] < val[y]) swap(x,y);
rs[x] = Un(rs[x], y);
swap(ls[x], rs[x]);
root[ls[x]] = root[rs[x]] = x;
root[x] = x;
return x;
}
void pop(int &x) {
x = Un(ls[x], rs[x]);
}
int top(int x) {
return val[x];
}
}heap;
int n, m;
int Find(int x) {
return root[x] == x ? x : root[x] = Find(root[x]);
}
void solve() {
while(~scanf("%d", &n)) {
heap.cc();
for (int i = 1 ; i <= n ; i   ) {
ll x; scanf("%lld", &x);
heap.val[i] = x;
root[i] = i;
}
scanf("%d", &m);
while(m --) {
int u, v;
scanf("%d%d", &u, &v);
int fu = Find(u), fv = Find(v);
if (fu == fv) puts("-1");
else {
heap.val[fu] >>= 1;
heap.val[fv] >>= 1;
heap.pop(root[u]); heap.pop(root[v]);
heap.ls[fu] = heap.rs[fu] = 0;
heap.ls[fv] = heap.rs[fv] = 0;
root[u] = heap.Un(fu, root[u]);
root[v] = heap.Un(fv, root[v]);
root[u] = heap.Un(root[u], root[v]);
printf("%d\n", heap.val[root[u]]);
}
}
}
}``````