swust2619 发表于 2018-04-11 | 分类于 算法 , 树 , 树链剖分 | 阅读数 次 链接:swust2619 题解 树链剖分,初始置为0,毁坏一个点置1 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667#include<iostream>#include<cstdio>#include<cstdlib>#include<cmath>#include<cstring>#include<algorithm>#define rep(i,x,y) for(register int i=x;i<=y;++i)#define repd(i,x,y) for(register int i=x;i>=y;--i)#define ll long long#define lowbit(x) x&(-x)using namespace std;const int N=2e5+50;int n,m,id[N],rt[N<<2],top[N],hson[N],size[N],deep[N],head[N],f[N],x,y,op,cnt;struct node{ int v,nxt; inline void init(int a,int b){v=a;nxt=b;}}e[N];inline void adde(int u,int v){ e[++cnt].init(v,head[u]); head[u]=cnt;}void dfs1(int x){ size[x]=1; for(int i=head[x],v;i;i=e[i].nxt)if((v=e[i].v)!=f[x]){ f[v]=x; deep[v]=deep[x]+1; dfs1(v); size[x]+=size[v]; if(size[hson[x]]<size[v])hson[x]=v; }}void dfs2(int x,int t){ top[x]=t;id[x]=++cnt; if(hson[x])dfs2(hson[x],t); for(int i=head[x],v;i;i=e[i].nxt)if(hson[x]!=(v=e[i].v)&&v!=f[x])dfs2(v,v);}inline void update(int x,int y){for(register int i=x;i<=n;i+=lowbit(i))rt[i]+=y;}inline int query(int x){int ans=0;for(register int i=x;i;i-=lowbit(i))ans+=rt[i];return ans;}inline int check(int x,int y){ while(top[x]!=top[y]){ if(deep[top[x]]<deep[top[y]])swap(x,y); if(query(id[x])-query(id[top[x]]-1))return 0; x=f[top[x]]; } if(id[x]<id[y])swap(x,y); return query(id[x])-query(id[y]-1)==0;}int main(){ scanf("%d%d",&n,&m); rep(i,2,n){ scanf("%d%d",&x,&y); adde(x,y);adde(y,x); } dfs1(1);cnt=0; dfs2(1,1); while(m--){ scanf("%d",&op); if(op==1){ scanf("%d%d",&x,&y); puts(check(x,y)?"YES":"NO"); } else if(op==2){scanf("%d",&x);update(id[x],-1);} else {scanf("%d",&x);update(id[x],1);} } return 0;}