分析，首先要查找一个认识的猴子群体（简称猴群）中力气最大的猴子，又要合并两个打完架的猴群，很明显是可并堆的性质，所以这题就是一个左偏树模板。那么套模板就可以了，不过注意，因为要把力气最大的猴子的力气减半，所以就先把它从猴群中删除，减半后放回去再求现在猴群中的力气最大值就可以了。
Code：
//It is made by HolseLee on 15th Mar 2018 //HDU 1512 #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<iostream> #include<iomanip> #include<algorithm> using namespace std; const int N=1e5+7; int n,m; struct Monkey { int val,dist; int ls,rs,fa; }t[N]; inline int read() { char ch=getchar(); int num=0;bool flag=false; while(ch<'0'||ch>'9') {if(ch=='-')flag=true; ch=getchar();} while(ch>='0'&&ch<='9') {num=num*10+ch-'0'; ch=getchar();} return flag?-num:num; } inline int find(int x) { return t[x].fa?find(t[x].fa):x; } inline int merge(int x,int y) { if(!x||!y)return x+y; if(t[x].val<t[y].val) swap(x,y); int &ul=t[x].ls,&ur=t[x].rs; ur=merge(ur,y); t[ur].fa=x; if(t[ul].dist<t[ur].dist)swap(ul,ur); t[x].dist=t[ur].dist+1; return x; } inline int erase(int x) { int ul=t[x].ls,ur=t[x].rs; t[x].dist=0;t[x].fa=0; t[x].ls=t[x].rs=0; t[ul].fa=0,t[ur].fa=0; return merge(ul,ur); } inline int push(int x,int y) { return merge(x,y); } int main() { while(~scanf("%d",&n)) { t[0].dist=-1; for(int i=1;i<=n;i++) { t[i].val=read(); t[i].ls=t[i].rs=0; t[i].dist=t[i].fa=0; } m=read();int x,y; for(int i=1;i<=m;i++) { x=read();y=read(); int fx=find(x),fy=find(y); if(fx!=fy) { t[fx].val/=2; int xx=push(erase(fx),fx); t[fy].val/=2; int yy=push(erase(fy),fy); printf("%d ",t[merge(xx,yy)].val); } else printf("-1 "); } } return 0; }