题目链接

#include<bits/stdc++.h>
using namespace std;
struct Node {
    int dist,value;
    Node *left=nullptr,*right=nullptr;
};
Node* meld(Node* x,Node* y) {
    if(x==nullptr)return y;
    if(y==nullptr)return x;
    if(x->value < y->value)swap(x,y);
    x->right = meld(x->right,y);
    if (!x->left || x->right->dist > x->left->dist) {
        swap(x->left,x->right);
    }
    if(x->right==nullptr)x->dist=1;
    else x->dist = x->right->dist+1;
    return x;
}
Node* insert(Node* x,int value) {
    Node* temp = new Node;
    temp->dist = 1;
    temp->value = value;
    return meld(x,temp);
}
Node* pop(Node* x) {
    Node* left = x->left;
    Node* right = x->right;
    delete x;
    return meld(left,right);
}
unordered_map<int,int>father;
unordered_map<int,Node*>node;
int find_root(int x) {
    if(father[x]==x)return x;
    return father[x] = find_root(father[x]);
}
void add(int x,int y) {
    int tx = find_root(x);
    int ty = find_root(y);
    if(tx==ty)return;
    father[tx] = ty;
    node[ty] = meld(node[tx],node[ty]);
}
int main()
{
    int n,m;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        int x;
        scanf("%d",&x);
        node[i] = insert(nullptr,x);
        father[i] = i;
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++) {
        int x,y;
        scanf("%d%d",&x,&y);
        int tx = find_root(x);
        int ty = find_root(y);
        if(tx==ty) {
            printf("-1\n");
            continue;
        }
        node[tx]->value /=2;
        node[ty]->value /=2;
        add(tx,ty);
        printf("%d\n",node[ty]->value);
    }
    return 0;
}