记录编号	427141	评测结果	AAAAAAAAAA
题目名称	526.[HDU 1512] 爱争吵的猴子	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.276 s
提交时间	2017-07-20 18:28:06	内存使用	1.84 MiB

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
struct node{
	node *l,*r;
	int v,h;
	node(int V){v=V;h=1;l=r=0;}
}*root[N];
node* merge(node *x,node *y){
	if (!x) return y;
	if (!y) return x;
	if (x->v<y->v) swap(x,y);
	x->r=merge(x->r,y);
	if (!x->l||x->r->h>x->l->h) swap(x->l,x->r);
	x->h=x->r?x->r->h+1:1;
	return x;
}
int fa[N];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int n,m;
int main()
{
	freopen("monkeyk.in","r",stdin);
	freopen("monkeyk.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;i++){
		int v;
		scanf("%d",&v);
		root[i]=new node(v);
		fa[i]=i;
	}
	scanf("%d",&m);
	for (int i=1;i<=m;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		u=find(u);v=find(v);
		if (u!=v){
			int topu=root[u]->v,topv=root[v]->v;
			root[u]=merge(root[u]->l,root[u]->r);
			root[u]=merge(root[u],new node(topu>>1));
			root[v]=merge(root[v]->l,root[v]->r);
			root[v]=merge(root[v],new node(topv>>1));
			root[u]=merge(root[u],root[v]);
			fa[v]=u;
			printf("%d\n",root[u]->v);
		}
		else puts("-1");
	}
	return 0;
}