撰写
In order to strengthen the defense ability, many stars in galaxy allied together and built many bidirectional tunnels to exchange messages. However, when the Galaxy War began, some tunnels were destroyed by the monsters from another dimension. Then many problems were raised when some of the stars wanted to seek help from the others.
In the galaxy, the stars are numbered from 0 to N-1 and their power was marked by a non-negative integer pi. When the star A wanted to seek help, it would send the message to the star with the largest power which was connected with star A directly or indirectly. In addition, this star should be more powerful than the star A. If there were more than one star which had the same largest power, then the one with the smallest serial number was chosen. And therefore, sometimes star A couldn’t find such star for help.
Given the information of the war and the queries about some particular stars, for each query, please find out whether this star could seek another star for help and which star should be chosen.
Input
There are no more than 20 cases. Process to the end of file.
For each cases, the first line contains an integer N (1 <= N <= 10000), which is the number of stars. The second line contains N integers p0, p1, … , pn-1 (0 <= pi <= 1000000000), representing the power of the i-th star. Then the third line is a single integer M (0 <= M <= 20000), that is the number of tunnels built before the war. Then M lines follows. Each line has two integers a, b (0 <= a, b <= N – 1, a != b), which means star a and star b has a connection tunnel. It’s guaranteed that each connection will only be described once.
In the (M + 2)-th line is an integer Q (0 <= Q <= 50000) which is the number of the information and queries. In the following Q lines, each line will be written in one of next two formats.
“destroy a b” – the connection between star a and star b was destroyed by the monsters. It’s guaranteed that the connection between star a and star b was available before the monsters’ attack.
“query a” – star a wanted to know which star it should turn to for help
There is a blank line between consecutive cases.
Output
For each query in the input, if there is no star that star a can turn to for help, then output “-1”; otherwise, output the serial number of the chosen star.
Print a blank line between consecutive cases.
Sample Input
2 10 20 1 0 1 5 query 0 query 1 destroy 0 1 query 0 query 1
Sample Output
1 -1 -1 -1
题意：给你n个点，以及点权，再给m条边，代笔两点之间连通。给q个询问，其中destroy a b 代表毁坏a，b之间的路，q a代表询问a所能求助的点的编号，注意，能被求助的点只能权值比求助点大，如果有多个答案，输出最小的点。
题解：首先是加边的问题，如何加边？只要按照权值进行合并即可，注意等于的时候按照编号大小合并，最后查询的时候不能以pre[i]！=i的条件判定是否有可求助点，因为有可能权值相同但是为了其他边的方便我们仍然连接了两条边，所以应该按照rank[find(a)]>rank[a]的条件来查询。
其次是如何删边，删边是不可能删边的，只有把它离线输入完再逆序判断加（本应该删除的边，但是被标记后没有加进来，所以在删除之间这边都应该存在）边才能维持的了生活这样子啦。
另外，因为值是小等于1e4的，所以用一个1e5的值去map与读入读出就行，这里要注意u应该大于v，否则万一u=0，后序判断就不太方便（好吧我懒）。
最后说一声，本题要求在两个样例之间输入空行，用变量控制输出就行。
代码：
#include<algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
const ll mod = 1000000007;
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
const int maxn = 1e5+5;
int pre[maxn];
int rank[maxn];
int sign[maxn];
int query[maxn];
map<int,int>ma;
const int hash=1e5;
int find(int x){
return pre[x]==x?x:pre[x]=find(pre[x]);
}
void unionn(int x,int y){
int fx=find(x);
int fy=find(y);
if(fx==fy)return;
if(rank[fx]>rank[fy]){
pre[fy]=fx;
}else if(rank[fx]<rank[fy]){
pre[fx]=fy;
}else{
if(fx>fy)pre[fx]=fy;
else pre[fy]=fx;
}
}
int main(){
int n,m,q,h=0;
while(scanf("%d",&n)==1){
ma.clear();
rep(i,0,n-1){
scanf("%d", &rank[i]);
pre[i]=i;
}
scanf("%d",&m);
int u,v;
rep(i,1,m){
scanf("%d%d", &u,&v);
if(u<v)swap(u,v);
sign[i]=hash*u+v;
}
char t[20];
scanf("%d", &q);
rep(i,1,q){
scanf("%s",t);
if(t[0]=='q'){
scanf("%d",&u);
query[i]=u;
}else{
scanf("%d%d", &u,&v);
if(u<v)swap(u,v);//一是为了顺序，另外怕0*1e5失去hash
ma[u*hash+v]=1;
query[i]=u*hash+v;
}
}
rep(i,1,m){
if(!ma[sign[i]])unionn(sign[i]/hash,sign[i]%hash);
}
per(i,1,q){
if(query[i]>=1e5){
unionn(query[i]/hash,query[i]%hash);
}else{
int temp=find(query[i]);
if(rank[temp]<=rank[query[i]])query[i]=-1;
else query[i]=temp;
}
}
if(h++)printf("\n");
rep(i,1,q){
if(query[i]<hash)
printf("%d\n", query[i]);
}
}
return 0;
}