[题目链接]
https://codeforces.com/contest/877/problem/E
[算法]
首先求出这棵树的DFS序
一棵子树的DFS序为连续的一段 ， 根据这个性质 ， 用线段树维护区间中1的个数即可
时间复杂度 : O(NlogN)
[代码]
#include<bits/stdc++.h> using namespace std; const int MAXN = 2e5 + 10; typedef long long ll; typedef long double ld; struct edge { int to , nxt; } e[MAXN << 2]; int n , q , timer , tot; int val[MAXN] , l[MAXN] , r[MAXN] , dfn[MAXN] , size[MAXN] , head[MAXN] , loc[MAXN] , par[MAXN]; struct Segment_Tree { struct Node { int l , r , cnt; bool tag; } a[MAXN << 2]; inline void update(int index) { a[index].cnt = a[index << 1].cnt + a[index << 1 | 1].cnt; } inline void build(int index , int l , int r) { a[index].l = l , a[index].r = r; a[index].tag = false; if (l == r) { a[index].cnt = (val[loc[l]] == 1); return; } int mid = (l + r) >> 1; build(index << 1 , l , mid); build(index << 1 | 1 , mid + 1 , r); update(index); } inline void pushdown(int index) { int l = a[index].l , r = a[index].r; int mid = (l + r) >> 1; if (a[index].tag) { a[index << 1].cnt = (mid - l + 1) - a[index << 1].cnt; a[index << 1 | 1].cnt = (r - mid) - a[index << 1 | 1].cnt; a[index << 1].tag ^= 1; a[index << 1 | 1].tag ^= 1; a[index].tag = false; } } inline void modify(int index , int l , int r) { if (a[index].l == l && a[index].r == r) { a[index].cnt = (r - l + 1) - a[index].cnt; a[index].tag ^= 1; return; } pushdown(index); int mid = (a[index].l + a[index].r) >> 1; if (mid >= r) modify(index << 1 , l , r); else if (mid + 1 <= l) modify(index << 1 | 1 , l , r); else { modify(index << 1 , l , mid); modify(index << 1 | 1 , mid + 1 , r); } update(index); } inline int query(int index , int l , int r) { if (a[index].l == l && a[index].r == r) return a[index].cnt; pushdown(index); int mid = (a[index].l + a[index].r) >> 1; if (mid >= r) return query(index << 1 , l , r); else if (mid + 1 <= l) return query(index << 1 | 1 , l , r); else return query(index << 1 , l , mid) + query(index << 1 | 1 , mid + 1 , r); } } SGT; template <typename T> inline void chkmax(T &x,T y) { x = max(x,y); } template <typename T> inline void chkmin(T &x,T y) { x = min(x,y); } template <typename T> inline void read(T &x) { T f = 1; x = 0; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - '0'; x *= f; } inline void addedge(int u , int v) { ++tot; e[tot] = (edge){v , head[u]}; head[u] = tot; } inline void dfs(int u) { l[u] = dfn[u] = ++timer; loc[timer] = u; for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].to; if (v == par[u]) continue; dfs(v); } r[u] = timer; } int main() { scanf("%d" , &n); for (int i = 2; i <= n; i++) { scanf("%d" , &par[i]); addedge(par[i] , i); } for (int i = 1; i <= n; i++) scanf("%d" , &val[i]); dfs(1); SGT.build(1 , 1 , n); scanf("%d" , &q); while (q--) { char type[5]; scanf("%s" , type); if (type[0] == 'p') { int u; scanf("%d" , &u); SGT.modify(1 , l[u] , r[u]); } else { int u; scanf("%d" , &u); printf("%d " , SGT.query(1 , l[u] , r[u])); } } return 0; }