题目链接：P1456 Monkey King

RT，蒟蒻写左偏树MLE了。

（代码输出答案是正确的，小数据AC了）

#include <iostream>
#include <cstdio>
using namespace std;

const int N = 1e5 + 10;
int n, m, fa[N];
struct node
{
	int val, dist, ls, rs;
	void clear()
	{
		dist = 1, ls = rs = 0;
		return;
	}
}t[N];

void read(int &s)
{
	s = 0; bool pd = false; char c = getchar();
	while (c < '0' || c > '9')
	{
		if (c == '-') pd = true;
		c = getchar();
	}
	while (c >= '0' && c <= '9')
	{
		s = (s << 3) + (s << 1) + (c ^ 48);
		c = getchar();
	}
	if (pd) s = -s;
	return;
}

int find(int x)
{
	if (fa[x] != x) fa[x] = find(fa[x]);
	return fa[x];
}

int merge(int x, int y)
{
	if (!x || !y) return x | y;
	if (t[x].val < t[y].val) swap(x, y);
	t[x].rs = merge(t[x].rs, y);
	if (t[t[x].ls].dist < t[t[x].rs].dist)
		swap(t[x].ls, t[x].rs);
	t[x].dist = t[t[x].rs].dist + 1;
	return x;
}

int main()
{
	while (~scanf("%d", &n))
	{
		for (int i = 1; i <= n; i++)
			fa[i] = i, t[i].val = 0, t[i].clear();
		for (int i = 1; i <= n; i++)
			read(t[i].val);
		read(m);
		for (int x, y, i = 1; i <= m; i++)
		{
			read(x), read(y);
			int fx = find(x), fy = find(y);
			if (fx == fy)
			{
				puts("-1");
				continue;
			}
			fa[t[fx].ls] = fa[t[fx].rs] = merge(t[fx].ls, t[fx].rs);
			t[fx].val /= 2, t[fx].clear();
			fa[fx] = fa[fa[t[fx].ls]] = merge(fx, fa[t[fx].ls]);
			fa[t[fy].ls] = fa[t[fy].rs] = merge(t[fy].ls, t[fy].rs);
			t[fy].val /= 2, t[fy].clear();
			fa[fy] = fa[fa[t[fy].ls]] = merge(fy, fa[t[fy].ls]);
			fa[fa[fx]] = fa[fa[fy]] = merge(fa[fx], fa[fy]);
			printf("%d\n", t[fa[fa[fx]]].val);
		}
	}
	return 0;
}