## luogu说我内容太长，所以只好分着发。
by Drifterming @ 2018-12-26 10:46:05
这是我将她的代码改成了并查集，可能调试的很乱
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1e5+5, M=1e5+5, P=1999997;
#define lc x<<1
#define rc x<<1|1
#define mid ((l+r)>>1)
#define lson lc, l, mid
#define rson rc, mid+1, r
typedef long long ll;
inline int read(){
char c=getchar();int x=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
int n, m, trn, mark[N], Q, c, x, y, del[M];
int Hash[P];
inline int& Map(int x) {return Hash[x%P];}
struct meow{int u, v;} a[M], tr[N];
struct qmeow{int c, u, v, qid;}q[M];
int ans[M];
struct Graph{
struct edge{int v, ne, id;} e[M<<1];
int cnt, h[N];
inline void ins(int u, int v, int id) {
e[++cnt]=(edge){v, h[u], id}; h[u]=cnt;
e[++cnt]=(edge){u, h[v], id}; h[v]=cnt;
}
int vis[N];
void dfs(int u) {
vis[u]=1;
for(int i=h[u];i;i=e[i].ne)
if(!vis[e[i].v]) {
mark[e[i].id]=1;
tr[++trn]=a[e[i].id];
dfs(e[i].v);
}
}
}G;
struct edge{int v, ne;} e[N<<1];
int cnt, h[N];
inline void ins(int u, int v) {
e[++cnt]=(edge){v, h[u]}; h[u]=cnt;
e[++cnt]=(edge){u, h[v]}; h[v]=cnt;
}
int dfn[N], dfc, fa[N], top[N], deep[N], mx[N], size[N];
void dfs(int u) {
size[u]=1;
for(int i=h[u];i;i=e[i].ne) {
int v=e[i].v;
if(v==fa[u]) continue;
deep[v]=deep[u]+1; fa[v]=u;
dfs(v);
size[u]+=size[v];
if(size[v]>size[mx[u]]) mx[u]=v;
}
}
void dfs2(int u, int anc) { //printf("u anc %d %d\n",u,anc);
dfn[u] = ++dfc; top[u] = anc;
if(mx[u]) dfs2(mx[u], anc);
for(int i=h[u];i;i=e[i].ne)
if(e[i].v != fa[u] && e[i].v != mx[u]) dfs2(e[i].v, e[i].v);
}
struct SegmentTree{
struct meow{
int sum, tag;
meow():tag(-1){}
}t[N<<2];
inline void paint(int x, int l, int r, int v) {
// cout<<x<<' '<<l<<' '<<r<<' '<<v<<'\n';
t[x].tag = v;
t[x].sum = (r-l+1)*v;
}
inline void pushDown(int x, int l, int r) {
if(t[x].tag != -1) {
paint(lson, t[x].tag);
paint(rson, t[x].tag);
t[x].tag = 0;
}
}
void build(int x, int l, int r) {
if(l==r) t[x].sum=1;
else {
build(lson); build(rson);
t[x].sum = t[lc].sum + t[rc].sum;
}
}
inline void cover(int x, int l, int r, int ql, int qr, int v) {
if(ql<=l && r<=qr) paint(x, l, r, v);
else {
pushDown(x, l, r);
if(ql<=mid) cover(lson, ql, qr, v);
if(mid<qr) cover(rson, ql, qr, v);
t[x].sum = t[lc].sum + t[rc].sum;
}
}
inline int que(int x, int l, int r, int ql, int qr) {
if(ql<=l && r<=qr) return t[x].sum;
else {
pushDown(x, l, r);
int ans=0;
if(ql<=mid) ans+=que(lson, ql, qr);
if(mid<qr) ans+=que(rson, ql, qr);
return ans;
}
}
int zz()
{
cout<<t[1].sum<<'\n';
}
}S;
void cover(int x, int y, int v) {
while(top[x] != top[y]) {
if(deep[top[x]] < deep[top[y]]) swap(x, y);
S.cover(1,1,n,dfn[top[x]],dfn[x],v);
x = fa[top[x]];
}
if(dfn[x] > dfn[y]) swap(x, y);
if(x!=y) S.cover(1,1,n,dfn[x]+1,dfn[y],v);
}
int query(int x, int y) {
int ans=0;
while(top[x] != top[y]) {
if(deep[top[x]] < deep[top[y]]) swap(x, y);
ans += S.que(1,1,n,dfn[top[x]],dfn[x]);
x = fa[top[x]];
}
if(dfn[x] > dfn[y]) swap(x, y);
if(x!=y) ans += S.que(1,1,n,dfn[x]+1,dfn[y]);
return ans;
}
int F[123456];
int find(int x)
{
return x==F[x]?x:F[x]=find(F[x]);
}
int main() {
freopen("6.in","r",stdin);
// freopen("466.out","w",stdout);
n=read(); m=read();
int T=21*n+67;
for(int i=1;i<=n;++i) F[i]=i;
for(int i=1; i<=m; i++) {
x=read(); y=read(); if(x>y) swap(x, y);
a[i]=(meow){x, y};
Map(x*n+y)=i;
// if(x==21&&y==67)
if(x*n+y==T)
cout<<x<<' '<<y<<' '<<Map(T)<<'\n';
}
cout<<Map(T)<<'\n';
int A=0;
while(true) {
c=read();
if(c==-1) break;
x=read(); y=read(); if(x>y) swap(x, y);
q[++Q]=(qmeow){c, x, y, 0};
if(c==0)del[ Map(x*n+y) ] = 1/*,cout<<x<<' '<<y<<' ',cout<<Map(x*n+y)<<'\n'*/;
else q[Q].qid = ++ans[0];
}
int kk=0;
for(int i=1; i<=m; i++)
{
if(del[i]) continue;
int q=find(a[i].u),p=find(a[i].v);
if(q==p) continue;
F[q]=p;mark[i]=1;
ins(a[i].u,a[i].v);++kk;
// G.ins(a[i].u, a[i].v, i); //printf("hi %d\n",i);
}
// cout<<kk<<'\n';
// G.dfs(1);
// cout<<A<<'\n';
// cout<<trn<<'\n';
// for(int i=1; i<=trn; i++) ins(tr[i].u, tr[i].v);// printf("tr %d %d\n",tr[i].u, tr[i].v);
dfs(1); dfs2(1, 1);
S.build(1, 1, n);
/*S.zz();*/int k=0;
for(int i=1; i<=m; i++)
if(!mark[i] && !del[i])
{
// cout<<i<<'\n';
cover(a[i].u, a[i].v, 0);
++k;
// cout<<a[i].u<<' '<<a[i].v<<'\n';
// cout<<a[i].u<<' '<<a[i].v<<'\n';
}
// cout<<k<<'\n';
// S.zz();
for(int i=Q; i>=1; i--) { //printf("Q %d\n",i);
if(q[i].c==0) cover(q[i].u, q[i].v, 0);
else ans[q[i].qid] = query(q[i].u, q[i].v);
}
// for(int i=1; i<=ans[0]; i++) printf("%d\n",ans[i]);
}
```
by Drifterming @ 2018-12-26 10:46:32
这是我用的stl的map
```cpp
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<map>
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
typedef long long LL;
inline int read()
{
char c=getchar();int num=0,f=1;
for(;!isdigit(c);c=getchar())
f=c=='-'?-1:f;
for(;isdigit(c);c=getchar())
num=num*10+c-'0';
return num*f;
}
const int N=1e5+5;
int n,m,C;
map<pii,int> ma;
bool cut[N];
int A[N],B[N];
int head[N],num_edge;
struct Edge
{
int v,nxt;
}edge[N<<1];
inline void add_edge(int u,int v)
{
edge[++num_edge].v=v;
edge[num_edge].nxt=head[u];
head[u]=num_edge;
}
struct OPT
{
int typ,a,b;
}opt[N];
int fa[N];
int find(int x)
{
return x==fa[x]?x:fa[x]=find(fa[x]);
}
struct NODE
{
int s,t,siz,dep;
int top,son,fa;
}node[N];
void dfs1(int u,int fa)
{
node[u].siz=1;
for(int i=head[u],v;i;i=edge[i].nxt)
{
v=edge[i].v;
if(v==fa) continue;
node[v].fa=u,node[v].dep=node[u].dep+1;
dfs1(v,u);
node[u].siz+=node[v].siz;
if(node[v].siz>node[node[u].son].siz)
node[u].son=v;
}
}
int bound;
void dfs2(int u,int top)
{
node[u].s=++bound;node[u].top=top;
if(node[u].son)
{
dfs2(node[u].son,top);
for(int i=head[u],v;i;i=edge[i].nxt)
{
v=edge[i].v;
if(v==node[u].fa||v==node[u].son)
continue;
dfs2(v,v);
}
}
node[u].t=bound;
}
#define Root tree[root]
#define lson tree[root].ls
#define rson tree[root].rs
#define Lson tree[lson]
#define Rson tree[rson]
struct Tree
{
int ls,rs,sum,tag;
}tree[N*2];
int Rt,now_node;
void build(int &root,int l,int r)
{
root=++now_node;Root.sum=r-l+1;
if(l==r)
return;
int mid=(l+r)>>1;
build(lson,l,mid),build(rson,mid+1,r);
}
void pushdown(int root)
{
Lson.tag=Rson.tag=1;
Lson.sum=Rson.sum=0;
Rson.tag=0;
}
void modify(int root,int l,int r,int L,int R)
{
if(l==L&&r==R){Root.sum=0,Root.tag=1;return;}
if(Root.tag) pushdown(root);
int mid=(l+r)>>1;
if(R<=mid) modify(lson,l,mid,L,R);
else if(L>mid) modify(rson,mid+1,r,L,R);
else modify(lson,l,mid,L,mid),modify(rson,mid+1,r,mid+1,R);
Root.sum=Lson.sum+Rson.sum;
}
int query(int root,int l,int r,int L,int R)
{
if(l==L&&r==R) return Root.sum;
if(Root.tag) pushdown(root);
int mid=(l+r)>>1;
if(R<=mid) return query(lson,l,mid,L,R);
else if(L>mid) return query(rson,mid+1,r,L,R);
else return query(lson,l,mid,L,mid)+query(rson,mid+1,r,mid+1,R);
}
void Modify(int x,int y)
{
int fx=node[x].top,fy=node[y].top;
while(fx!=fy)
{
if(node[fx].dep<node[fy].dep)
swap(x,y),swap(fx,fy);
modify(1,1,n,node[fx].s,node[x].s);
x=node[fx].fa,fx=node[x].top;
}
if(x==y) return;
if(node[x].dep>node[y].dep) swap(x,y);
modify(1,1,n,node[x].s+1,node[y].s);
}
int Query(int x,int y)
{
int res=0,fx=node[x].top,fy=node[y].top;
while(fx!=fy)
{
if(node[fx].dep<node[fy].dep)
swap(x,y),swap(fx,fy);
res+=query(1,1,n,node[fx].s,node[x].s);
x=node[fx].fa,fx=node[x].top;
}
if(x==y) return res;
if(node[x].dep>node[y].dep) swap(x,y);
return res+query(1,1,n,node[x].s+1,node[y].s);
}
int Ans[N],ans;
int main()
{
freopen("6.in","r",stdin);
// freopen("233.out","w",stdout);
n=read(),m=read();
for(int i=1;i<=n;++i)
fa[i]=i;
for(int i=1;i<=m;++i)
{
A[i]=read(),B[i]=read();
if(A[i]>B[i]) swap(A[i],B[i]);
if(A[i]==21&&B[i]==67)
cout<<i<<'\n';
ma[mp(A[i],B[i])]=i;
}
cout<<ma[mp(21,67)]<<'\n';
for(int a;;)
{
a=read();if(a==-1) break;
opt[++C].typ=a,opt[C].a=read(),opt[C].b=read();
if(opt[C].a>opt[C].b) swap(opt[C].a,opt[C].b);
if(opt[C].typ==0) //破坏边
{
// cout<<opt[C].a<<' '<<opt[C].b<<' ';
// cout<<ma[mp(opt[C].a,opt[C].b)]<<'\n';
cut[ma[mp(opt[C].a,opt[C].b)]]=1;
}
}
int zz=0;
for(int i=1,u,v;i<=m;++i) //造棵生成树
{
if(cut[i]) continue; //被破坏了
u=find(A[i]),v=find(B[i]);
if(u!=v) //还没联通，连起来
{
add_edge(A[i],B[i]),add_edge(B[i],A[i]);
fa[u]=v;cut[i]=1;
}
}
dfs1(1,1),dfs2(1,1);
build(Rt,1,n);
// cout<<tree[1].sum<<'\n';
for(int i=1;i<=m;++i) //消除非树边的影响
{
if(cut[i]) continue;
Modify(A[i],B[i]);
++zz;
// cout<<i<<'\n';
// cout<<A[i]<<' '<<B[i]<<'\n';
}
// cout<<zz<<'\n';
// cout<<no<<'\n'<<tmp<<'\n';
// cout<<tree[1].sum<<'\n';
for(int i=C;i;--i)
{
if(opt[i].typ==0)
Modify(opt[i].a,opt[i].b);
else
Ans[++ans]=Query(opt[i].a,opt[i].b);
}
// for(int i=ans;i;--i)
// cout<<Ans[i]<<'\n';
return 0;
}
```
如果有哪位大佬能解答，蒟蒻不胜感激，改了一上午了qwq。
by Drifterming @ 2018-12-26 10:47:09
Orz
by xenonex @ 2018-12-26 10:53:06
求解啊Orz 好像是hash冲突了
by Drifterming @ 2018-12-26 15:28:14