每次给出要争吵的猴子a和b，用并查集判断如果他们是朋友输出-1
如果不是，找出a，b在的堆的根A，B，分别合并A，B的左右孩子，再合并一下。
之后把A，B的数据更改一下：权值除以2，左右孩子设为0，再插入到堆中即可。
最后输出堆顶。
1 #include2 #include 3 4 using namespace std; 5 6 int n, m; 7 int f[100010], w[100010], d[100010], l[100010], r[100010]; 8 9 inline int merge(int x, int y)10 {11 if(!x || !y) return x + y;12 if(w[x] < w[y]) swap(x, y);13 r[x] = merge(r[x], y);14 f[r[x]] = x;15 if(d[l[x]] < d[r[x]]) swap(l[x], r[x]);16 d[x] = d[r[x]] + 1;17 return x;18 }19 20 inline int find(int x)21 {22 return x == f[x] ? x : f[x] = find(f[x]);23 }24 25 inline int pop(int x)26 {27 int lc = l[x], rc = r[x];28 f[lc] = lc;29 f[rc] = rc;30 l[x] = r[x] = d[x] = 0;31 return merge(lc, rc);32 }33 34 int main()35 {36 int i, j, x, y, fx, fy, x1, y1;37 while(~scanf("%d", &n))38 {39 for(i = 1; i <= n; i++)40 {41 scanf("%d", &w[i]);42 f[i] = i;43 l[i] = 0;44 r[i] = 0;45 d[i] = 0;46 }47 scanf("%d", &m);48 for(i = 1; i <= m; i++)49 {50 scanf("%d %d", &x, &y);51 fx = find(x);52 fy = find(y);53 if(fx == fy)54 {55 printf("-1\n");56 continue;57 }58 x1 = pop(fx);59 w[fx] /= 2;60 x1 = merge(x1, fx);61 y1 = pop(fy);62 w[fy] /= 2;63 y1 = merge(y1, fy);64 printf("%d\n", w[merge(x1, y1)]);65 }66 }67 return 0;68 }