目录
codeforces 877E Danil and a Part-time Job题意：题解：Code：
codeforces 877E Danil and a Part-time Job
题目传送门
题意：
给出一个树，每一个点都有权值，权值为0或1，要求支持两个操作：子树权值翻转，子树权值和。
题解：
比较水的一道E题吧，反正就是用线段树维护\(Dfn\)序就行了，差不多树剖那个套路吧。。
Code：
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+500;
int idx[N],x[N],v[N],sz[N],heav[N];
int n,cnt,q;
vector<int>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<r) Modify(rs(o),l,r);
Update(o);
return ;
}
int Query(int o,int l,int r) {
if(t[o].l>=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<r) ans+=Query(rs(o),l,r);
return ans;
}
}
using namespace SegmentTree;
namespace Solver {
void Dfs1(int o,int fa) {
sz[o]=1;
int Mxson=-1;
for(int i=0;i<(int)G[o].size();i++) {
int to=G[o][i];
if(to==fa) continue;
Dfs1(to,o);
sz[o]+=sz[to];
if(sz[to]>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;
}
转载于:https://www.cnblogs.com/Apocrypha/p/9742667.html
