题解

链接

题解

这题是TYB的博客过来的。。
于是就看到了离线+树链剖分几个字。。
不知道算不算膜了题解
反正觉得挺简单的

我们考虑离线。。
就可以把删边变为加边了。。
由于题目保证无论怎么样，点点连通
所以我们可以先构造出一个树
然后每一次，如果多了条边，就把这两个端点之间的树边都标为不是关键便就好了

update:
忽然想起自己忘记打lazy了QAQ
然而我还是A了。。
看的人知道就好

CODE：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
const int M=100005*2;
const int N=100005*2;
map<pair<int,int>,int> p;
int n,m;
int X[M],Y[M];
struct qt
{int op;int x,y;
}s[N];
bool ok[N];//这个东西死了没 
int q;
int f[N];
struct qq
{int x,y,last;//树边 
}e[N];int num,last[N];
int find (int x) {
   return f[x]==x?f[x]:f[x]=find(f[x]);}
void init (int x,int y) 
{num++;e[num].x=x;e[num].y=y;e[num].last=last[x];last[x]=num;
}
int ys[N],tot[N],son[N],fa[N],dep[N],top[N],num2;
void dfs (int x,int ff)
{tot[x]=1;for (int u=last[x];u!=-1;u=e[u].last){int y=e[u].y;if (y==ff) continue;dep[y]=dep[x]+1;fa[y]=x;dfs(y,x);tot[x]+=tot[y];if (tot[son[x]]<tot[y]) son[x]=y;}
}
void dfs1 (int x,int tp)
{ys[x]=++num2;top[x]=tp;if (son[x]!=0) dfs1(son[x],tp);for (int u=last[x];u!=-1;u=e[u].last){int y=e[u].y;if (y==son[x]||y==fa[x]) continue;dfs1(y,y);}
}
struct qy
{int l,r;int s1,s2;int c;
}tr[N*2];
void bt (int l,int r)
{int a=++num;tr[a].l=l;tr[a].r=r;tr[a].c=(r-l+1);if (l==r) return ;int mid=(l+r)>>1;tr[a].s1=num+1;bt(l,mid);tr[a].s2=num+1;bt(mid+1,r);
}
void change (int now,int l,int r)
{if (tr[now].l==tr[now].r){tr[now].c=0;return ;}int s1=tr[now].s1,s2=tr[now].s2;int mid=(tr[now].l+tr[now].r)>>1;if (r<=mid) change(s1,l,r);else if (l>mid) change(s2,l,r);else change(s1,l,mid),change(s2,mid+1,r);tr[now].c=tr[s1].c+tr[s2].c;
}
void Change (int x,int y)//这两个点的那啥 
{int tx=top[x],ty=top[y];if (dep[tx]>dep[ty]) {swap(x,y);swap(tx,ty);}//让y来跳while (tx!=ty){change(1,ys[top[y]],ys[y]);y=fa[top[y]];ty=top[y];if (dep[tx]>dep[ty]) {swap(x,y);swap(tx,ty);}//让y来跳}if (x==y) return ;if (dep[x]>dep[y]) swap(x,y);change(1,ys[son[x]],ys[y]);
}
void BT ()
{dep[1]=1;fa[1]=0;dfs(1,0);/* printf("Als1");for (int u=1;u<=n;u++) printf("%d ",fa[u]);*/num2=0;dfs1(1,1);// printf("Als2");num=0;bt(1,num2);for (int u=1;u<=m;u++){if (ok[u]==false) continue;int x=X[u],y=Y[u];Change(x,y);}
}
int ans[40005];
void Ins ()
{num=0;memset(last,-1,sizeof(last));scanf("%d%d",&n,&m);for (int u=1;u<=m;u++){int x,y;scanf("%d%d",&x,&y);X[u]=x;Y[u]=y;p[make_pair(x,y)]=p[make_pair(y,x)]=u;}memset(ok,true,sizeof(ok));while (true){int op;scanf("%d",&op);if (op==-1) break;q++;s[q].op=op;scanf("%d%d",&s[q].x,&s[q].y);if (op==0)//破坏ok[p[make_pair(s[q].x,s[q].y)]]=false; }
}
void bt_e()
{for (int u=1;u<=n;u++) f[u]=u;for (int u=1;u<=m;u++){if (ok[u]==false) continue;int x=X[u],y=Y[u];int fx=find(x),fy=find(y);if (fx==fy) continue;f[fx]=fy;ok[u]=false;init(x,y);init(y,x);}
}
int get (int now,int l,int r)
{if (tr[now].l==l&&tr[now].r==r)return tr[now].c;int s1=tr[now].s1,s2=tr[now].s2;int mid=(tr[now].l+tr[now].r)>>1;if (r<=mid) return get(s1,l,r);else if (l>mid) return get(s2,l,r);else return get(s1,l,mid)+get(s2,mid+1,r);
}
int get_ans (int x,int y)//这两个点的那啥 
{int tx=top[x],ty=top[y];if (dep[tx]>dep[ty]) {swap(x,y);swap(tx,ty);}//让y来跳int cnt=0;while (tx!=ty){cnt=cnt+get(1,ys[top[y]],ys[y]);y=fa[top[y]];ty=top[y];if (dep[tx]>dep[ty]) {swap(x,y);swap(tx,ty);}//让y来跳}if (x==y) return cnt;if (dep[x]>dep[y]) swap(x,y);return cnt+get(1,ys[son[x]],ys[y]);
}
void solve ()
{for (int u=q;u>=1;u--){if (s[u].op==0)Change(s[u].x,s[u].y);else    ans[++ans[0]]=get_ans(s[u].x,s[u].y);}for (int u=ans[0];u>=1;u--)printf("%d\n",ans[u]);
}
int main()
{Ins();bt_e();
// printf("YES1");BT();
// printf("YES2");solve();return 0;
}