树剖WA10pts求条
查看原帖
树剖WA10pts求条
573334
yzkadbq_qwq楼主2024/11/28 20:42
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=250001;
struct edge{
	int v,c,next;
} e[N<<1];
int h[N],tot=0;
void addedge(int u,int v,int c){
	e[++tot]={v,c,h[u]};
	h[u]=tot;
	return;
}
int a[N],size[N],son[N],dep[N],fa[N];
int dfs1(int u,int f){
	size[u]=1,son[u]=-1;
	for(int i=h[u];i;i=e[i].next){
		if(e[i].v!=fa[u]){
			dep[e[i].v]=dep[u]+1;
			fa[e[i].v]=u;
			size[u]+=dfs1(e[i].v,u);
			a[e[i].v]=e[i].c;
			if(son[u]==-1 or size[son[u]]<size[e[i].v]) son[u]=e[i].v;
		}
	}
	return size[u];
}
int cnt=0,dfn[N],top[N];
void dfs2(int u,int t){
	top[u]=t,dfn[u]=++cnt;
	if(son[u]==-1) return; 
	dfs2(son[u],t);
	for(int i=h[u];i;i=e[i].next){
		if(e[i].v!=son[u] and e[i].v!=fa[u]){
			dfs2(e[i].v,e[i].v);
		}
	}
	return;
}
struct node{
	int l,r,sum;
	bool tag;
} t[N<<3];
int buildtree(int x,int l,int r){
	t[x].l=l,t[x].r=r;
	if(l==r) return t[x].sum=a[l]; 
	int mid=(l+r)>>1;
	return t[x].sum=buildtree(x<<1,l,mid)+buildtree(x<<1|1,mid+1,r);
}
void update(int x){
	t[x].sum=(t[x<<1].tag?0:t[x<<1].sum+t[x<<1|1].tag?0:t[x<<1|1].sum);
	return;
}
void pushdown(int x){
	if(t[x].tag){
		t[x<<1].tag=t[x<<1|1].tag=1;
		t[x].sum=t[x].tag=0;
	}
	return;
}
void change(int x,int l,int r){
	if(t[x].l>r or t[x].r<l) return;
	if(t[x].l>=l and t[x].r<=r){
		t[x].tag=1;
		return;
	}
	pushdown(x);
	change(x<<1,l,r),change(x<<1|1,l,r);
	update(x);
	return;
}
int query(int x,int l,int r){
	if(t[x].l>r or t[x].r<l) return 0;
	if(t[x].l>=l and t[x].r<=r) return t[x].tag?0:t[x].sum;
	pushdown(x);
	int res=query(x<<1,l,r)+query(x<<1|1,l,r);
	update(x);
	return res;
}
int lca(int x,int y){
	while(top[x]!=top[y]){
		if(dep[top[x]]>dep[top[y]]) x=fa[top[x]];
		else y=fa[top[y]];
	}
	if(dep[x]<dep[y]) return x;
	else return y; 
}
void changet(int x,int y){
	while(top[x]!=top[y]){
		// cout<<x<<" "<<y<<endl;
		if(dep[top[x]]>dep[top[y]]) change(1,dfn[top[x]],dfn[x]),x=fa[top[x]];
		else change(1,dfn[top[y]],dfn[y]),y=fa[top[y]];
	}
	if(dep[x]>dep[y]) change(1,dfn[y]+1,dfn[x]);
	else change(1,dfn[x]+1,dfn[y]);
	return;
}
int queryt(int x,int y){
	int ans=0;
	while(top[x]!=top[y]){
		// cout<<x<<" "<<y<<endl;
		if(dep[top[x]]>dep[top[y]]) ans+=query(1,dfn[top[x]],dfn[x]),x=fa[top[x]];
		else ans+=query(1,dfn[top[y]],dfn[y]),y=fa[top[y]];
	}
	if(dep[x]>dep[y]) ans+=query(1,dfn[y]+1,dfn[x]);
	else ans+=query(1,dfn[x]+1,dfn[y]);
	return ans;
}
int n,m;
void print(){
	for(int i=1;i<=2*n;i++){
		cout<<i<<" "<<t[i].l<<" "<<t[i].r<<" "<<t[i].tag<<" "<<t[i].sum<<"\n";
	}
	cout<<endl;
	return;
}
signed main(){
	cin>>n;
	for(int i=1;i<n;i++){
		int u,v,c;
		cin>>u>>v;
		addedge(u,v,1),addedge(v,u,1);
		// cout<<endl;
		// for(int i=1;i<=n;i++){
		// 	for(int j=h[i];j;j=e[j].next){
		// 		cout<<i<<"->"<<e[j].v<<":"<<e[i].c<<endl;
		// 	}
		// }
	}
	dep[1]=1;
	dfs1(1,0);
	dfs2(1,1);
	buildtree(1,1,n);
	// for(int i=1;i<=n;i++){
	// 	cout<<i<<" "<<dfn[i]<<" "<<top[i]<<endl;
	// }
	// cout<<endl;
	cin>>m;
	// print();
	for(int i=1;i<=n+m-1;i++){
		char op;
		do{
			op=getchar();
		}while(op!='A' and op!='W');
		// cout<<op;
		if(op=='A'){
			int l,r;
			cin>>l>>r;
			changet(l,r);
		}
		if(op=='W'){
			int x;
			cin>>x;
			cout<<queryt(1,x)<<endl;
		}
		// print();
	}
	return 0;
}
2024/11/28 20:42
加载中...