Assume that every money has a strongness value, which will be reduced to only half of the original after a duel(that is, 10 will be reduced to 5 and 5 will be reduced to 2).
And we also assume that every monkey knows himself. That is, when he is the strongest one in all of his friends, he himself will go to duel.
First part: The first line contains an integer N(N<=100,000), which indicates the number of monkeys. And then N lines follows. There is one number on each line, indicating the strongness value of ith monkey(<=32768).
Second part: The first line contains an integer M(M<=100,000), which indicates there are M conflicts happened. And then M lines follows, each line of which contains two integers x and y, indicating that there is a conflict between the Xth monkey and Yth.
20
16
10
10
4
5
2 3
3 4
3 5
4 5
1 5
5
5
-1
10
可并堆裸题，没什么思维难度。只要学会了就会打了.
代码：
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<stdlib.h>
const int MANX=;
using namespace std;
int fa[MANX],r[MANX],l[MANX],v[MANX],d[MANX];
int n,m; void cl(){
for(int i=;i<=n;i++) fa[i]=i;
memset(r,,sizeof(r));
memset(l,,sizeof(l));
memset(v,,sizeof(v));
} int find(int x){
if(fa[x]!=x) fa[x]=find(fa[x]);
return fa[x];
} int merge(int x,int y){
if(!x) return y;
if(!y) return x;
if(v[x]<v[y]) swap(x,y);
r[x]=merge(r[x],y);fa[r[x]]=x;
if(d[r[x]]>d[l[x]]) swap(l[x],r[x]);
else d[x]=d[r[x]]+;//
return x;
} int del(int x){
int lz=l[x],rz=r[x];
l[x]=r[x]=d[x]=;fa[lz]=lz,fa[rz]=rz;
return merge(lz,rz);
} int main(){
while(scanf("%d",&n)!=EOF){
cl();
for(int i=;i<=n;i++) scanf("%d",&v[i]);
scanf("%d",&m);
for(int i=;i<=m;i++){
int x,y;scanf("%d%d",&x,&y);
int ll=find(x),rr=find(y);
if(ll==rr){printf("-1\n");}
else{
v[ll]/=,v[rr]/=;
int lz=del(ll),rz=del(rr);
lz=merge(ll,lz),rz=merge(rz,rr);
printf("%d\n",v[merge(lz,rz)]);
}
}
}
}