codeforces 343D 树剖后odt维护

时间:2023-03-09 16:01:31
codeforces 343D 树剖后odt维护

子树修改+路径修改+单点查询

树链剖分+区间维护即可

由于只有单点查询,我直接用了odt,复杂度还行

#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
#define ull unsigned long long
#define fi first
#define se second
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define rep(ii,a,b) for(int ii=a;ii<=b;++ii)
#define per(ii,a,b) for(int ii=b;ii>=a;--ii)
#define forn(ii,x) for(int ii=head[x];ii;ii=e[ii].next)
using namespace std;
const int maxn=5e5+20,maxm=2e6+10;
const int INF=0x3f3f3f3f;
const ll mod=1e9+7;
//head
int casn,n,m,k;
int num[maxn];
namespace odt{
struct segnode{
int l,r;mutable int val;
bool operator<(const segnode &b)const {return l<b.l;}
};
set<segnode> nd;
#define iter set<segnode>::iterator
auto split(int pos){
auto it=nd.lower_bound({pos,pos,0});
if(it!=nd.end()&&it->l==pos) return it;
it--;
int l=it->l,r=it->r,val=it->val;
nd.erase(it);nd.insert({l,pos-1,val});
return nd.insert({pos,r,val}).fi;
}
void update(int l,int r,int val){
auto itr=split(r+1);auto itl=split(l);
nd.erase(itl,itr);nd.insert({l,r,val});
}
int query(int pos){
auto it=nd.lower_bound({pos,pos,0});
if(it!=nd.end()&&it->l==pos) return it->val;
it--;
return it->val;
}
} namespace gg{
struct node{int to,next;}e[maxn<<1];
int head[maxn],nume,mp[maxn];
void add(int a,int b){e[++nume]={b,head[a]};head[a]=nume;}
int ltop[maxn],fa[maxn],deep[maxn];
int sz[maxn],remp[maxn];
int son[maxn],cnt,out[maxn];
void dfs1(int now,int pre,int d){
deep[now]=d,fa[now]=pre,sz[now]=1;son[now]=0;
forn(i,now) {int to=e[i].to;
if(to!=pre){
dfs1(to,now,d+1);sz[now]+=sz[to];
if(sz[to]>sz[son[now]]) son[now]=to;
}
}
}
void dfs2(int now,int pre,int sp){
ltop[now]=sp;mp[now]=++cnt;remp[cnt]=now;
if(son[now]) dfs2(son[now],now,sp);
forn(i,now){
int to=e[i].to;
if(to!=son[now]&&to!=pre) dfs2(to,now,to);
}
}
void update1(int a){odt::update(mp[a],mp[a]+sz[a]-1,1);}
void update2(int now){
while(now>1){
int l=max(mp[ltop[now]],2),r=mp[now];
if(l<=r) odt::update(l,r,0);
now=fa[ltop[now]];
}
}
} int main() {
IO;
cin>>n;
odt::nd.insert({1,n,0});
m=n-1;
while(m--){int a,b;
cin>>a>>b;
gg::add(a,b);
gg::add(b,a);
}
gg::dfs1(1,1,0);
gg::dfs2(1,0,1);
cin>>m;
while(m--){int a,b;
cin>>a>>b;
if(a==1) gg::update1(b);
if(a==2) gg::update2(b);
if(a==3) cout<<odt::query(gg::mp[b])<<endl;
}
}