题目链接：
题解：显然一看就感觉要么树链剖分要么线段树+dfs序，题目要求的操作显然用线段树+dfs序就可以实现。然后就敲一下线段树+dfs序就行挺简单的只要dfs一遍记录当前节点的下表然后再加一个leng数组来存子树最多到达几然后更新或者求值的时候只要查询(pos[x],leng[x])即可。
#include#include #include #include #define lson (i << 1)#define rson ((i << 1) | 1)using namespace std;const int M = 2e5 + 10;int a[M] , pos[M] , leng[M] , pre[M] , cnt;vector vc[M];struct TnT { int l , r , sum , lazy;}T[M << 2];void push_up(int i) { T[i].sum = T[lson].sum + T[rson].sum;}void push_down(int i) { if(T[i].lazy) { T[lson].sum = T[lson].r - T[lson].l + 1 - T[lson].sum; T[rson].sum = T[rson].r - T[rson].l + 1 - T[rson].sum; T[lson].lazy ^= 1; T[rson].lazy ^= 1; T[i].lazy = 0; }}void build(int l , int r , int i) { int mid = (l + r) >> 1; T[i].l = l , T[i].r = r , T[i].sum = 0 , T[i].lazy = 0; if(l == r) { T[i].sum = a[pre[l]]; return ; } push_down(i); build(l , mid , lson); build(mid + 1 , r , rson); push_up(i);}void update(int l , int r , int i) { int mid = (T[i].l + T[i].r) >> 1; if(T[i].l == l && T[i].r == r) { T[i].sum = (T[i].r - T[i].l + 1) - T[i].sum; T[i].lazy ^= 1; return ; } push_down(i); if(mid < l) { update(l , r , rson); } else if(mid >= r) { update(l , r , lson); } else { update(l , mid , lson) , update(mid + 1 , r , rson); } push_up(i);}int query(int l , int r , int i) { int mid = (T[i].l + T[i].r) >> 1; if(T[i].l == l && T[i].r == r) { return T[i].sum; } push_down(i); if(mid < l) { return query(l , r , rson); } else if(mid >= r) { return query(l , r , lson); } else { return query(l , mid , lson) + query(mid + 1 , r , rson); }}void dfs(int u) { int len = vc[u].size(); for(int i = 0 ; i < len ; i++) { int v = vc[u][i]; pos[v] = ++cnt; pre[cnt] = v; dfs(v); leng[v] = cnt; }}int main() { int n , x , q; char s[123]; scanf("%d" , &n); for(int i = 2 ; i <= n ; i++) { scanf("%d" , &x); vc[x].push_back(i); } for(int i = 1 ; i <= n ; i++) { scanf("%d" , &a[i]); } scanf("%d" , &q); cnt = 0; pos[1] = ++cnt; pre[cnt] = 1; leng[1] = n; dfs(1); build(1 , n , 1); while(q--) { scanf("%s" , s); if(s[0] == 'g') { scanf("%d" , &x); printf("%d\n" , query(pos[x] , leng[x] , 1)); } else { scanf("%d" , &x); update(pos[x] , leng[x] , 1); } } return 0;}