给一个有根树,1e5个节点,每个节点有权值0/.1,
1e5操作:
1.将一个点的子树上所有点权值取反
2.查询一个点的子树的权值和
 
题解:
先深搜整颗树,用dfs序建立每个点对应的区间,
等于把树拍扁成一个数列,每次操作从就对点变成了对区间
然后就是裸线段树
注意拍扁后的节点标号和原来的树节点标号是不等价的,要映射一下
#include <bits/stdc++.h>
#define endl '\n'
#define ll long long
#define fi first
#define se second
#define pii pair<int,int>
#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)
using namespace std;
const int maxn=1e6+7;
int casn,n,m,k;
vector<int>g[maxn];
pii seg[maxn];
int vis[maxn];
int a[maxn];
int dfn;
void dfs(int now){
seg[now].fi=++dfn;
vis[dfn]=now;
for(auto i:g[now]) dfs(i);
seg[now].se=dfn;
}
class segtree{
#define nd node[now]
#define ndl node[now<<1]
#define ndr node[now<<1|1]
public:
struct segnode {
int l,r;int sum,tag;
int mid(){return (r+l)>>1;}
int len(){return r-l+1;}
void update(){sum=len()-sum;tag^=1;}
};
vector<segnode> node;
int cnt;
segtree(int n) {node.resize(n<<2|3);maketree(1,n);}
void pushup(int now){nd.sum=ndl.sum+ndr.sum;}
void pushdown(int now){
if(nd.tag){
ndl.update();
ndr.update();
nd.tag=0;
}
}
void maketree(int s,int t,int now=1){
nd={s,t,0,0};
if(s==t){
nd.sum=a[vis[s]];
return ;
}
maketree(s,nd.mid(),now<<1);
maketree(nd.mid()+1,t,now<<1|1);
pushup(now);
}
void update(int s,int t,int now=1){
if(s>nd.r||t<nd.l) return ;
if(s<=nd.l&&t>=nd.r){nd.update();return ;}
pushdown(now);
update(s,t,now<<1); update(s,t,now<<1|1);
pushup(now);
}
int query(int s,int t,int now=1){
if(s>nd.r||t<nd.l) return 0;
if(s<=nd.l&&t>=nd.r) return nd.sum;
pushdown(now);
return query(s,t,now<<1)+query(s,t,now<<1|1);
}
};
int main() {
IO;
cin>>n;
rep(i,2,n){
int a;cin>>a;
g[a].push_back(i);
}
dfs(1);
rep(i,1,n) cin>>a[i];
segtree tree(n);
cin>>m;
string s;
int x;
while(m--){
cin>>s>>x;
if(s=="get")cout<<tree.query(seg[x].fi,seg[x].se)<<endl;
else tree.update(seg[x].fi,seg[x].se);
}
return 0;
}

最新文章

  1. 测试dockerfile
  2. 仿SGI STL的traits技法
  3. log4j介绍以及使用教程
  4. window 安装Mysql 5.6 发生系统错误 1067
  5. C++经典编程题#2:大象喝水
  6. UICollectionView 浅析
  7. idea 给maven项目添加依赖(二)
  8. 转:【Java并发编程】之二十三:并发新特性—信号量Semaphore(含代码)
  9. POJ1988 Cube stacking(非递归)
  10. HDU 5968(异或计算 暴力)
  11. 总结Jquery中获取自定义属性使用.attr()和.data()以及.prop()的区别
  12. expdp和impdp 使用注意事项
  13. Intellij IDEA 通过数据库表逆向生成带注释的实体类文件超级详细步骤,附详细解决方案
  14. 基础数据类型的坑和集合及深浅copy
  15. ui设计教程分享:关于Logo设计要素
  16. [批处理]自动修改本机IP地址
  17. Ant—怎样Windows操作系统中搭建Apache Ant环境
  18. Linux-&gt;apt-包的位置和变更
  19. divison in python2 and python3
  20. 第三章 服务治理: Spring Cloud Eureka

热门文章

  1. 采用ADM2483磁隔离器让RS485接口更简单更安全
  2. Surjectivity is stable under base change
  3. 微信JSSDK使用步骤(用于在微信浏览器中自定义分享,分享到朋友圈,拍照,扫一扫等功能)
  4. CentOS 7 下面使用 sendMail 发送邮件
  5. jsp中【&lt;%=request.getContextPath()%&gt;】项目路径
  6. Python进阶3---python类型注解、functools
  7. Shell命令-系统信息及显示之uname、hostname
  8. Java中反射机制详解
  9. Python——迭代器
  10. MySQL字符串进行加减乘除的运算