目录

codeforces 877E Danil and a Part-time Job

题意：

给出一个树，每一个点都有权值，权值为0或1，要求支持两个操作：子树权值翻转，子树权值和。

题解：

比较水的一道E题吧，反正就是用线段树维护\(Dfn\)序就行了，差不多树剖那个套路吧。。

Code：

#include
    
     using namespace std;const int N=2e5+500;int idx[N],x[N],v[N],sz[N],heav[N];int n,cnt,q;vector
     
      G[N];namespace SegmentTree {  struct node {    int l,r,sz,cnt,flip;  }t[N<<3];#define ls(o) (o)<<1#define rs(o) (o)<<1|1  void Update(int o) {    t[o].cnt=t[ls(o)].cnt+t[rs(o)].cnt;  }  void Pushdown(int o) {    if(!t[o].flip) return ;    t[ls(o)].cnt=t[ls(o)].sz-t[ls(o)].cnt;    t[rs(o)].cnt=t[rs(o)].sz-t[rs(o)].cnt;    t[ls(o)].flip^=1;    t[rs(o)].flip^=1;    t[o].flip^=1;    return ;  }  void Build(int o,int l,int r) {    t[o].l=l;t[o].r=r;t[o].sz=r-l+1;    if(l==r) {      t[o].cnt=v[l];      return ;    }    int mid=(l+r)>>1;    Build(ls(o),l,mid);    Build(rs(o),mid+1,r);    Update(o);    return ;  }  void Modify(int o,int l,int r) {    if(t[o].l>=l&&t[o].r<=r) {      t[o].cnt=t[o].sz-t[o].cnt;      t[o].flip^=1;      return ;    }    Pushdown(o);    int mid=(t[o].l+t[o].r)>>1;    if(mid>=l) Modify(ls(o),l,r);    if(mid
      
       =l&&t[o].r<=r) return t[o].cnt;    Pushdown(o);    int mid=(t[o].l+t[o].r)>>1;    int ans=0;    if(mid>=l) ans+=Query(ls(o),l,r);    if(mid
       
        Mxson) {    Mxson=sz[to];    heav[o]=to;      }    }  }  void Dfs2(int o) {    idx[o]=++cnt;    v[cnt]=x[o];    if(!heav[o]) return ;    Dfs2(heav[o]);    for(int i=0;i<(int)G[o].size();i++) {      int to=G[o][i];      if(idx[to]) continue;      Dfs2(to);    }  }  void Init() {    Dfs1(1,1);    Dfs2(1);    Build(1,1,n);  }  void Change(int o) {Modify(1,idx[o],idx[o]+sz[o]-1);}  int Ask(int o) {return Query(1,idx[o],idx[o]+sz[o]-1);}}int main() {  scanf("%d",&n);  for(int i=2,p;i<=n;i++) {    scanf("%d",&p);    G[p].push_back(i);    G[i].push_back(p);  }  for(int i=1;i<=n;i++) scanf("%d",&x[i]);  Solver::Init();  scanf("%d",&q);  while(q--) {    char s[10];    int x;    scanf("%s%d",s,&x);    if(s[0]=='g') printf("%d\n",Solver::Ask(x));    else Solver::Change(x);  }  return 0;}