link 题意：给一无向连通图，每个点有一个权值，q次操作 每次操作有两种 1,v 寻找v所在连通块内权值最大的点，并输出这个权值并且把改点权值变成0 2.x 删掉第i条边
思路： 查询图上连通块内最大值和修改我们只学过在一棵树上利用dfs序，然后线段树维护。 那么考虑如何将此题转化成一棵树。 我们把删边考虑为倒着加边。在加边过程中利用并查集维护连通块。并且将每一时刻每一个点的连通块转化为一颗’子树’，这样在查询的时候就可以通过查询子树点权最大值来得到结果。 如何将各个时刻的连通块转化为一颗树？ 只需要在加边的过程中，新增一个点连向那两个点的连通块的祖先，那么不断进行该过程即可得到一颗重构树。
WA： 数组开小会wa，递归死循环会MLE 。 for循环找dfs序时，由于是从每个点的祖先找，所以if里应该用pos判断，dfn存储的是 第i个位置的数，不能用了判断i有没有被访问过
#include <bits/stdc++.h> #define ls rt<<1 #define rs rt<<1|1 #define pb push_back using namespace std; typedef long long ll; const int maxn = 7e5 + 5; const int mod = 1e9 + 7; int n,m,q; int p[maxn],u[300010],v[300010],vis[300010],fa[maxn],op[500010][2],sz[maxn],boss[500010]; int pos[maxn],dfn[maxn],tot; struct node {int w,pos;}t[maxn<<2]; vector<int>G[maxn]; int fid(int x){return x==fa[x]?x:fa[x]=fid(fa[x]); } void dfs(int u) { pos[u]=++tot; dfn[tot]=u; sz[u]=1; for(int v:G[u]) dfs(v),sz[u]+=sz[v]; } void push_up(int rt) { if(t[ls].w>t[rs].w) t[rt]=t[ls]; else t[rt]=t[rs]; } void build(int rt,int l,int r) { t[rt].w=t[rt].pos=0; if(l==r) { t[rt].w=p[dfn[l]]; //cout<<l<<','<<t[rt].w<<','<<dfn[l]<<endl; t[rt].pos=l; return ; } int mid=l+r>>1; build(ls,l,mid); build(rs,mid+1,r); push_up(rt); } void upd(int rt,int l,int r,int z) { if(l==r&&r==z) { t[rt].w=0; return ; } int mid=l+r>>1; if(z<=mid) upd(ls,l,mid,z); else upd(rs,mid+1,r,z); push_up(rt); } node ask(int rt,int l,int r,int ql,int qr) {//cout<<ql<<','<<qr<<endl; if(ql<=l&&r<=qr) return t[rt]; int mid=l+r>>1; node f1,f2; f1.w=f2.w=f1.pos=f2.pos=0; if(ql<=mid) f1=ask(ls,l,mid,ql,qr); if(qr>mid) f2=ask(rs,mid+1,r,ql,qr); if(f1.w>f2.w) return f1; else return f2; } int main() { scanf("%d%d%d",&n,&m,&q); for(int i=1;i<=n;i++) { scanf("%d",&p[i]); } for(int i=1;i<=m;i++) { scanf("%d%d",&u[i],&v[i]); } for(int i=1;i<=q;i++) { scanf("%d%d",&op[i][0],&op[i][1]); if(op[i][0]==2) vis[op[i][1]]=1; } for(int i=1;i<=n+q;i++) fa[i]=i; for(int i=1;i<=m;i++) { if(vis[i]) continue; //cout<<i<<endl; int fx=fid(u[i]),fy=fid(v[i]); if(fx!=fy) { fa[fx]=fy; G[fy].pb(fx); } } //for(int i=1;i<=n;i++) cout<<fid(i)<<',';cout<<endl; for(int i=q;i>=1;i--) { if(op[i][0]==2) { int x=op[i][1]; int fx=fid(u[x]),fy=fid(v[x]); if(fx!=fy) { n++; G[n].pb(fx); G[n].pb(fy); fa[fx]=n; fa[fy]=n; //cout<<i<<endl; } } else boss[i]=fid(op[i][1]); } //for(int i=1;i<=n;i++) cout<<fid(i)<<',';cout<<endl;return 0; for(int i=1;i<=n;i++) { if(!dfn[pos[i]]) { //cout<<i<<'_'<<fid(i)<<endl; dfs(fid(i)); } } //return 0; build(1,1,tot); /* cout<<tot<<','; for(int i=1;i<=tot;i++) printf("%d ",dfn[i]); printf("\n");*/ for(int i=1;i<=q;i++) { if(op[i][0]==1) { node x=ask(1,1,tot,pos[boss[i]],pos[boss[i]]+sz[boss[i]]-1); // if(x.w>0) upd(1,1,tot,x.pos); printf("%d\n",x.w); } } return 0; }