给一个有根树,1e5个节点,每个节点有权值0/.1,

1e5操作:

1.将一个点的子树上所有点权值取反

2.查询一个点的子树的权值和

 

题解:

先深搜整颗树,用dfs序建立每个点对应的区间,

等于把树拍扁成一个数列,每次操作从就对点变成了对区间

然后就是裸线段树

注意拍扁后的节点标号和原来的树节点标号是不等价的,要映射一下

#include 
       
        #define endl '\n'#define ll long long#define fi first#define se second#define pii pair
        
         #define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)#define rep(ii,a,b) for(int ii=a;ii<=b;++ii)using namespace std;const int maxn=1e6+7;int casn,n,m,k;vector
         
          g[maxn];pii seg[maxn];int vis[maxn];int a[maxn];int dfn;void dfs(int now){    seg[now].fi=++dfn;    vis[dfn]=now;    for(auto i:g[now]) dfs(i);    seg[now].se=dfn;}class segtree{#define nd  node[now]#define ndl node[now<<1]#define ndr node[now<<1|1]    public:    struct segnode {        int l,r;int sum,tag;        int mid(){return (r+l)>>1;}        int len(){return r-l+1;}        void update(){sum=len()-sum;tag^=1;}    };    vector
          
            node;    int cnt;    segtree(int n) {node.resize(n<<2|3);maketree(1,n);}    void pushup(int now){nd.sum=ndl.sum+ndr.sum;}    void pushdown(int now){        if(nd.tag){            ndl.update();            ndr.update();            nd.tag=0;        }    }    void maketree(int s,int t,int now=1){        nd={s,t,0,0};        if(s==t){            nd.sum=a[vis[s]];            return ;        }        maketree(s,nd.mid(),now<<1);        maketree(nd.mid()+1,t,now<<1|1);        pushup(now);    }    void update(int s,int t,int now=1){        if(s>nd.r||t
           
            =nd.r){nd.update();return ;}        pushdown(now);        update(s,t,now<<1); update(s,t,now<<1|1);        pushup(now);    }    int query(int s,int t,int now=1){        if(s>nd.r||t
            
             =nd.r) return nd.sum; pushdown(now); return query(s,t,now<<1)+query(s,t,now<<1|1); }};int main() { IO; cin>>n; rep(i,2,n){ int a;cin>>a; g[a].push_back(i); } dfs(1); rep(i,1,n) cin>>a[i]; segtree tree(n); cin>>m; string s; int x; while(m--){ cin>>s>>x; if(s=="get")cout<
             
              <