Graph and Queries

题目大意:

给一个\(n\)(1<=n<=2e5)个点,\(m\)(1<=m<=3e5)条边的无向图。有q(1<=q<=5e5)组询问。询问的格式有两种

1. 1 v 输入1可以到达的点的最大值，并将此值赋0
2. 2 v 删除第v条边

题目要求对于每一个第一类的询问输出所查询到的值。

问题分析：

对于图上最值查询问题可以考虑将其转化为区间查询。因为树上的最值查询利用dfs序容易转化为区间查询。但是很显然，题目中没有给出一颗树，查询的对象也不是某结点的子树。而且不仅伴随和点值更新，还伴随着边的更新。
当遇到集合相关的问题时，很自然的可以想到并查集。但并查集只支持合并的操作，不支持删除，在这个题目中只有删除操作。可以换个方向想，把删除操作倒过来做就是合并操作了。认真思考可以发现，在合并的过程中可以将题目中的图转化成满足下面条件的一棵树：

• 每一棵子树对应合并过程中某一时刻的一个连通块。

具体做法是在合并\((x,y)\)时新建一个结点\(v\),建立两条边\((v,x)\),\((v,y)\),并且在并查集中将使par[find(x)]=v,par[find(y)]=v;那么此时以v为根的子树就代表了在(x,y)连通之后x，y所在联通块。同时对于每一个第一类的询问，在合并之后，也要转化为对v的询问(或者在某一合并过程中将v合并成一个更大的子树u，那就是对u的询问)。

处理询问的过程可以用dfs序与线段树解决。

代码：

#include
using namespace std;
typedef long long LL;
typedef pairpii;
const int MAX_N=2e6+20;
const int INF=0x3f3f3f3f;
int n,m,q;
int arr[MAX_N];
pii e[MAX_N],que[MAX_N];
int del[MAX_N];
int par[MAX_N];
int tin[MAX_N],tout[MAX_N];
int tree[MAX_N*4];
vectorV[MAX_N];

int vis[MAX_N];
int find_p(int x){
    if(par[x]==x)return x;
    else{
        return par[x]=find_p(par[x]);
    }
}
void unite(int x,int y){
    x=find_p(x),y=find_p(y);
    if(x==y)return;

    n++;
    par[n]=n;
    par[x]=n,par[y]=n;
    V[n].push_back(x),V[n].push_back(y);
  //  V[x].push_back(n),V[y].push_back(n);
}
void update(int nod,int l,int r,int k,int v){
    if(l==r){
        tree[nod]=v;
        return;
    }
    int mid=(l+r)/2;
    if(k<=mid){
        update(nod*2,l,mid,k,v);
    }
    else{
        update(nod*2+1,mid+1,r,k,v);
    }
    tree[nod]=max(tree[nod*2],tree[nod*2+1]);

}
int query(int nod,int l,int r,int ll,int rr){
    if(l==ll&&r==rr){
        return tree[nod];
    }
    int mid=(l+r)/2;
    if(mid>=rr){
        return query(nod*2,l,mid,ll,rr);
    }
    else if(mid=1;i--){
        if(que[i].first==2){
            int v=que[i].second;
            unite(e[v].first,e[v].second);
        }
        else{
            que[i].second=find_p(que[i].second);
        }
    }
    //cout<<"***"<