[NOI2021] 轻重边
具体思路
树剖维护一下即可。
Code
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
struct edge{
int x,y,pre;
}a[2*N];
int last[N],alen;
int n,m;
void ins(int x,int y){//建边
a[++alen]=edge{x,y,last[x]};
last[x]=alen;
}
struct tnode{
int fa,dep,son,siz,top,id;
}t[N];
inline void dfs1(int x,int fa){//树剖板子
t[x]=tnode{fa,t[fa].dep+1,0,1,0,0};
for(int k=last[x];k;k=a[k].pre){
int y=a[k].y;
if(y==fa)continue;
dfs1(y,x);
t[x].siz+=t[y].siz;
if(t[t[x].son].siz<t[y].siz){
t[x].son=y;
}
}
}
int cnt,pos[N];
inline void dfs2(int x,int top){//树剖板子
t[x].top=top;
t[x].id=++cnt;
pos[cnt]=x;
if(t[x].son)dfs2(t[x].son,top);
for(int k=last[x];k;k=a[k].pre){
int y=a[k].y;
if(y!=t[x].fa&&y!=t[x].son){
dfs2(y,y);
}
}
}
struct trnode{
int l,r,lc,rc;
int c,tag,tsp;
//c表示当前区间重边数
//tag表示当前区间是重边还是轻边
//tsp表示当前区间是什么时候修改的
}tr[2*N];
int trlen;
inline void update(int now,int tag,int tsp){//更新信息
if(tag)tr[now].tag=tag;
if(tag==1){
tr[now].c=tr[now].r-tr[now].l+1;
}
else if(tag==-1){
tr[now].c=0;
}
if(tsp)tr[now].tsp=tsp;
}
inline void pushdown(int now,int lc,int rc){ //信息下放
update(lc,tr[now].tag,tr[now].tsp);
update(rc,tr[now].tag,tr[now].tsp);
tr[now].tag=tr[now].tsp=0;
}
inline void pushup(int now,int lc,int rc){//信息上传
tr[now].c=tr[lc].c+tr[rc].c;
}
inline void build(int nl,int nr){//建树
trlen++;int now=trlen;
tr[now]=trnode{nl,nr,-1,-1,0,0,0};
if(nl==nr)tr[now].c=0;
else{
int mid=(nl+nr)>>1;
tr[now].lc=trlen+1;build(nl,mid);
tr[now].rc=trlen+1;build(mid+1,nr);
pushup(now,tr[now].lc,tr[now].rc);
}
}
inline void change(int now,int nl,int nr,int l,int r,int c,int tsp){//修改当前区间,c=1为重边，c=-1为轻边
if(l<=nl&&nr<=r){
update(now,c,tsp);
return;
}
int mid=(nl+nr)>>1;
int lc=tr[now].lc,rc=tr[now].rc;
pushdown(now,lc,rc);
if(l<=mid)change(lc,nl,mid,l,r,c,tsp);
if(mid<r)change(rc,mid+1,nr,l,r,c,tsp);
pushup(now,lc,rc);
}
inline int query(int now,int nl,int nr,int l,int r){//查询当前区间重边数
if(l<=nl&&nr<=r){
return tr[now].c;
}
int mid=(nl+nr)>>1;
int lc=tr[now].lc,rc=tr[now].rc;
pushdown(now,lc,rc);
int res=0;
if(l<=mid)res+=query(lc,nl,mid,l,r);
if(mid<r)res+=query(rc,mid+1,nr,l,r);
return res;
}
inline int find(int now,int nl,int nr,int x){//查询当前点的修改时间
if(nl==nr){
return tr[now].tsp;
}
int mid=(nl+nr)>>1;
int lc=tr[now].lc,rc=tr[now].rc;
pushdown(now,lc,rc);
if(x<=mid)return find(lc,nl,mid,x);
else return find(rc,mid+1,nr,x);
}
inline void modify(int x,int y,int tsp){
while(t[x].top!=t[y].top){
if(t[t[x].top].dep<t[t[y].top].dep)
swap(x,y);
if(t[x].son){
change(1,1,n,t[t[x].son].id,t[t[x].son].id,-1,0);
}
change(1,1,n,t[t[x].top].id,t[x].id,1,tsp);
x=t[t[x].top].fa;
}
if(t[x].dep<t[y].dep)swap(x,y);
if(t[y].son&&t[t[y].son].dep<=t[x].dep){
change(1,1,n,t[t[y].son].id,t[x].id,1,tsp);
}
change(1,1,n,t[y].id,t[y].id,-1,tsp);
if(t[x].son){
change(1,1,n,t[t[x].son].id,t[t[x].son].id,-1,0);
}
}
inline int solve(int x,int y,int tsp){
int ans=0;
while(t[x].top!=t[y].top){
if(t[t[x].top].dep<t[t[y].top].dep)
swap(x,y);
if(t[t[x].top].fa){
int tsp1=find(1,1,n,t[t[t[x].top].fa].id);
int tsp2=find(1,1,n,t[t[x].top].id);
if(tsp1&&tsp2&&tsp2<tsp1){
change(1,1,n,t[t[x].top].id,t[t[x].top].id,-1,0);
}
}
ans=ans+query(1,1,n,t[t[x].top].id,t[x].id);
x=t[t[x].top].fa;
}
if(t[x].dep<t[y].dep)swap(x,y);
if(t[y].son&&t[t[y].son].dep<=t[x].dep){
ans+=query(1,1,n,t[t[y].son].id,t[x].id);
}
return ans;
}
int main(){
int T;scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
alen=1;memset(last,0,sizeof(last));
for(int i=1;i<n;i++){
int x,y;scanf("%d%d",&x,&y);
ins(x,y),ins(y,x);
}
t[0]=tnode{0,0,0,0,0,0};cnt=0;
dfs1(1,0),dfs2(1,1);
trlen=0;build(1,n);
for(int i=1;i<=m;i++){
int op,x,y;scanf("%d",&op);
if(op==1){
scanf("%d%d",&x,&y);
modify(x,y,i);
}
if(op==2){
scanf("%d%d",&x,&y);
printf("%d\n",solve(x,y,i));
}
}
}
return 0;
}