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

树链剖分+区间维护即可

由于只有单点查询,我直接用了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;
}
}

最新文章

  1. WCF备忘录一:服务端实例的生命周期
  2. 通过cygwin安装openSSH
  3. call指令的一个细节
  4. jni的使用方法
  5. Spring MVC 文件上传
  6. 使用lftp传输文件的shell脚本
  7. EL 表达式
  8. openerp学习笔记 自定义小数精度(小数位数)
  9. 每天2个android小例子----简单计算器源代码
  10. ural 1123
  11. linux 客户端与linux服务器端连接与文件上传下载
  12. MySQL源码之两阶段提交
  13. 【Objective-C基础教程-读书笔记】第1章 启程
  14. 关于数据库一致改关闭下redo日志文件丢失的处理办法的总结
  15. Spring框架快速入门之简介
  16. poj2909 || poj2262
  17. vue下拉列表
  18. Android和H5进行数据交互,Android获取H5Input框中的内容
  19. NodeJS操作Redis实现消息的发布与订阅
  20. 纯CSS3实现漂亮的价格表样式代码

热门文章

  1. CodeForces Round #554 Div.2
  2. 数据结构排序算法插入排序Java实现
  3. Linux(Ubuntu)使用日记------markdown文件与pdf,doc,docx文件的相互转化(pandoc使用)
  4. git总结一、工作中常用基础命令
  5. seaborn库
  6. 【DeepLearning】优化算法:SGD、GD、mini-batch GD、Moment、RMSprob、Adam
  7. c语言利用读取命令行(多行读取)
  8. Stars project
  9. 数据分析三剑客之numpy
  10. [POI2015]KIN[线段树]