模板题

#include<iostream>
#include<vector>
using namespace std;
const int N=5e5+9;
int n;
//树剖
//1.转成线性部分
vector<int> e[N];
void add(int u,int v){e[u].push_back(v);e[v].push_back(u);
}
int fa[N],dep[N],sz[N],wc[N];
void dfs1(int u,int f){//fa dep sz wcfa[u]=f;sz[u]=1;dep[u]=dep[f]+1;for(auto & i : e[u]){if(i!=f){dfs1(i,u);sz[u]+=sz[i];if(sz[i]>sz[wc[u]]){wc[u]=i;}}}
}
int dfn[N],rdfn[N],top[N],vistime;
void dfs2(int u,int Top){//dfn rdfn topdfn[u]=++vistime;rdfn[vistime]=u;top[u]=Top;if(wc[u]){dfs2(wc[u],Top);for(auto & i : e[u]){if(i!=wc[u] && i!=fa[u]){dfs2(i,i);}}}
}
//2.线段树维护
struct SEG{#define INF (1<<31)#define ll long long#define tl(id) (id<<1)#define tr(id) (id<<1|1)#define li inlinestruct node{int val,tag;}seg[N<<2];#define pushup(id) seg[id].val=seg[tl(id)].val+seg[tr(id)].valli int inrange(int L,int R,int l,int r){return l<=L && R<=r;}li int outofrange(int L,int R,int l,int r){return L>r || R<l;}li void build(const int id,int l,int r){seg[id].tag=INF;if(l==r){seg[id].val=0;return;}int mid=(l+r)>>1;build(tl(id),l,mid);build(tr(id),mid+1,r);pushup(id);}li void maketag(int id,int l,int r,ll v){seg[id].val=(r-l+1)*v;seg[id].tag=v;}li void pushdown(int id,int l,int r){if(seg[id].tag==INF){return;}int mid=(l+r)>>1;maketag(tl(id),l,mid,seg[id].tag);maketag(tr(id),mid+1,r,seg[id].tag);seg[id].tag=INF;}li ll query(int id,int L,int R,int l,int r){if(inrange(L,R,l,r)){return seg[id].val;}else if(!outofrange(L,R,l,r)){int mid=(L+R)>>1;pushdown(id,L,R);return (query(tl(id),L,mid,l,r)+query(tr(id),mid+1,R,l,r));}else{return 0;}}li void modify(int id,int L,int R,int l,int r,ll x){if(inrange(L,R,l,r)){maketag(id,L,R,x);}else if(!outofrange(L,R,l,r)){int mid=(L+R)>>1;pushdown(id,L,R);modify(tl(id),L,mid,l,r,x);modify(tr(id),mid+1,R,l,r,x);pushup(id);}}
}t;
//3.找LCA，同时完成操作
void update(int u,int v,int z){while(top[u]!=top[v]){if(dep[top[u]]<dep[top[v]]){//swap(u,v);}t.modify(1,1,n,dfn[top[u]],dfn[u],z);//深度越小，dfs序号越小u=fa[top[u]];//处理完上移动}t.modify(1,1,n,min(dfn[u],dfn[v]),max(dfn[u],dfn[v]),z);
}
ll ask(int u,int v){ll res=0;while(top[u]!=top[v]){if(dep[top[u]]<dep[top[v]]){swap(u,v);}res+=t.query(1,1,n,dfn[top[u]],dfn[u]);u=fa[top[u]];}res+=t.query(1,1,n,min(dfn[u],dfn[v]),max(dfn[u],dfn[v]));return res;
}
int main(){cin>>n;for(int i=1;i<=n-1;i++){int u,v;cin>>u>>v;add(u,v);}dfs1(1,0);dfs2(1,1);t.build(1,1,n);int m;cin>>m;for(int i=1;i<=m;i++){int op;cin>>op;if(op==1){int u;cin>>u;t.modify(1,1,n,dfn[u],dfn[u]+sz[u]-1,1);}else if(op==2){int u;cin>>u;update(1,u,0);}else{int u;cin>>u;cout<<t.query(1,1,n,dfn[u],dfn[u])<<'\n';}}return 0;
}

题外话，状态不好，不要写，不然板子题都会写bug,瞪眼法看了半小时看不出来重新写直接ac了

服了