CF-877-E-dfs序+线段树

877-E 题目大意

给定一颗\(n\)个节点的树，根为\(1\)，点带权，权值要么为0，要么为1。

\(q\)次询问，两种类型：

• \(get \space x\):询问\(x\)的子树中有多少个\(1\)。
• \(pow \space x\):将\(x\)子树中所有的值取反。

---

Solution

dfs序+线段树模板题，把子树上的操作转化为区间上的操作。

时间复杂度：\(O(nlogn)\)。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;const int N=2e5+10;
struct node{int l,r;int sum,tag;
}tr[N<<2];void pushup(int u){tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}void pushdown(int u){if(tr[u].tag){tr[u<<1].tag^=1;tr[u<<1].sum=tr[u<<1].r-tr[u<<1].l+1-tr[u<<1].sum;tr[u<<1|1].tag^=1;tr[u<<1|1].sum=tr[u<<1|1].r-tr[u<<1|1].l+1-tr[u<<1|1].sum;tr[u].tag=0;}
}void build(int u,int l,int r){tr[u]={l,r,0,0};if(l==r) return;int m=(l+r)>>1;build(u<<1,l,m);build(u<<1|1,m+1,r);
}void modify(int u,int l,int r){if(l<=tr[u].l&&tr[u].r<=r){tr[u].sum=tr[u].r-tr[u].l+1-tr[u].sum;tr[u].tag^=1;return;}pushdown(u);int m=(tr[u].l+tr[u].r)>>1;if(l<=m) modify(u<<1,l,r);if(r>m) modify(u<<1|1,l,r);pushup(u);
}int query(int u,int l,int r){if(l<=tr[u].l&&tr[u].r<=r){return tr[u].sum;}pushdown(u);int m=(tr[u].l+tr[u].r)>>1;int res=0;if(l<=m) res+=query(u<<1,l,r);if(r>m) res+=query(u<<1|1,l,r);return res;
}int main(){ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n;cin>>n;vector<vector<int>> e(n);vector<int> L(n),R(n);int dfn=0;for(int i=1;i<n;i++){int p;cin>>p;p--;e[p].push_back(i);}function<void(int)> dfs=[&](int x){L[x]=++dfn;for(auto y:e[x]){dfs(y);}R[x]=dfn;};dfs(0);build(1,1,n);for(int i=0;i<n;i++){int w;cin>>w;if(w) modify(1,L[i],L[i]);}int q;cin>>q;while(q--){string op;int x;cin>>op>>x;x--;if(op=="get"){cout<<query(1,L[x],R[x])<<'\n';}else{modify(1,L[x],R[x]);}}return 0;
}