记录编号	108293	评测结果	AAAAAAAAAA
题目名称	[HDU 1512] 爱争吵的猴子	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	0.381 s
提交时间	2014-07-03 18:30:38	内存使用	2.60 MiB

#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

priority_queue<int> h[100001];

int x,y,z;
int fa[100001];
int ans,n,m;
int siz[100001];

int find(int x)
{
	return fa[x]==x ? x : fa[x]=find(fa[x]);
}

void turn_map(int x,int y)
{
	while(!h[y].empty())
	{
		h[x].push(h[y].top());
		h[y].pop();
	}
}

int make_it(int x,int y)
{
	if(find(x)==find(y)) return -1;
	else
	{
		int r1=find(x);
		int r2=find(y);
		
		int xr=h[r1].top(); h[r1].pop();
		int yr=h[r2].top(); h[r2].pop();
		
		if(siz[r1]<siz[r2])
		{
			swap(r1,r2);
		}
		
		turn_map(r1,r2);
		
		if(r1!=r2)
		{
			siz[r1]+=siz[r2];
			fa[r2]=r1;
			siz[r2]=0;
		}
		
		h[r1].push(xr/2); h[r1].push(yr/2);
		
		return h[r1].top();
	}
}

void init(void)
{
	scanf("%d",&n);
	
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&x);
		
		h[i].push(x);
		fa[i]=i;
		siz[i]=1;
	}
	
	scanf("%d",&m);
	
	for(int i=1;i<=m;i++)
	{
		ans=-1;
		scanf("%d%d",&x,&y);
		printf("%d\n",make_it(x,y));
	}
}

int main()
{
	freopen("monkeyk.in","r",stdin);
	freopen("monkeyk.out","w",stdout);
 
	init();
	
	return 0;
}