Submission #3387789

---

Source Code Expand

#include <iostream>
#include <stdio.h>
#include <fstream>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <limits.h>
#include <math.h>
#include <functional>
#include <bitset>

#define repeat(i,n) for (long long i = 0; (i) < (n); ++ (i))
#define debug(x) cerr << #x << ": " << x << '\n'
#define debugArray(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i] << '\n'
#define debugArrayP(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i].first<< " " << x[i].second << '\n'

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> Pii;
typedef vector<int> vint;
typedef vector<ll> vll;
const ll INF = INT_MAX;
const ll MOD = 1e9+7;

struct HLDecomposition{
public:
    int V;
    vector<vint> g;
    vint dep,par,head,size,inv;
    vint in,out;
    HLDecomposition(int size_)
    :V(size_),g(V),dep(V,0),par(V,-1),head(V),size(V),inv(V),in(V),out(V),t(0){}

    void add_edge(int u,int v){
        g[u].push_back(v);
        g[v].push_back(u);
    }
    void build(int root=0){
        par[root]=0;
        dfs_size(root);
        par[root]=-1;
        dfs_hld(root);
    }

    int lca(int u,int v){
        while(1){
            if(in[u]>in[v])swap(u,v);
            if(head[u]==head[v])return u;
            v=par[head[v]];
        }
    }

    int distance(int u,int v){
        return dep[u]+dep[v]-2*dep[lca(u,v)];
    }

    int operator[](const int &k){
      return in[k];
    }
private:
    int t;
    void dfs_size(int v=0){
        size[v]=1;
        for(int& u:g[v]){
            if(par[u]>=0)continue;
            par[u]=v;
            dfs_size(u);
            size[v]+=size[u];
            if(size[u]>size[g[v][0]]){
                swap(u,g[v][0]);
            }
        }
    }
    void dfs_hld(int v=0){
        in[v] = t++;
        inv[in[v]]=v;
        for(int& u:g[v]){
            if(par[u]!=v)continue;
            head[u]=(u==g[v][0]?head[v]:u);
            dfs_hld(u);
        }
        out[v]=t;
    }
};




template<typename T>
struct segtree {
    int N;
    vector<T> node;
    //-------------書くとこ-------------------
    //単位元　ex)INF,0
    T default_value = 1;
    static inline T merge(const T& l, const T& r) {
        return l&r;
    }
    //----------------------------------------
    segtree(int n) {
        for(N=1;N<n;N*=2);
        node.resize(2 * N, default_value);
    }
    segtree(vector<int> v) {
        int sz = v.size();
        for(N=1;N<sz;N*=2);
        node.resize(2 * N, default_value);
        for (int i = 0; i < sz; i++)
            node[i + N - 1] = v[i];
        for (int i = N - 2; i >= 0; i--)
            node[i] = merge(node[2 * i + 1], node[2 * i + 2]);
    }
    void init(int k, T val) {
        k += N - 1; // leaf
        node[k] = val;
        while (k > 0) {
            k = (k - 1) / 2;
            node[k] = merge(node[k * 2 + 1], node[k * 2 + 2]);
        }
    }
    // update k th element
    void update(int k) {
        k += N - 1; // leaf
        node[k] ^= 1;
        while (k > 0) {
            k = (k - 1) / 2;
            node[k] = merge(node[k * 2 + 1], node[k * 2 + 2]);
        }
    }
    // [a, b)
    T query(int a, int b, int k=0, int l=0, int r=-1) {
      if(r<0)r=N;
        if (r <= a or b <= l)
            return default_value;
        if (a <= l and r <= b)
            return node[k];
        int m = (l + r) / 2;
        T vl = query(a, b, k * 2 + 1, l, m);
        T vr = query(a, b, k * 2 + 2, m, r);
        return merge(vl, vr);
    }

    T operator[](const int &k) {
        return node[k + N - 1];
    }
};


int main(){
  int N;cin>>N;
  HLDecomposition hld(N);
  vint p(N);
  p[0]=-1;
  repeat(i,N-1){
    cin>>p[i+1];p[i+1]--;
    hld.add_edge(i+1,p[i+1]);
  }
  hld.build();
  //debugArray(hld,N);
  segtree<ll> seg(N);
  vint C(N);
  repeat(i,N){
    cin>>C[i];
  }
  repeat(i,N-1){
    seg.init(hld[i+1],C[p[i+1]]!=C[i+1]);
  }
  debugArray(seg,N);
  int Q;cin>>Q;
  repeat(q,Q){
    int op,u;cin>>op>>u;u--;
    if(op==1){
      seg.update(hld[u]);
      //debugArray(seg,N);
    }else{
      int v;cin>>v;v--;
      bool isok=true;
      while(1){
        if(hld[u]>hld[v])swap(u,v);
        if(hld.head[u]!=hld.head[v]){
          isok &= seg.query(hld[hld.head[v]],hld[v]+1);
          v = hld.par[hld.head[v]];
        }else{
          if(u!=v)isok &= seg.query(hld[u]+1,hld[v]+1);
          break;
        }
      }
      cout << (isok? "YES":"NO") << endl;
    }
  }
  return 0;
}

Submission Info

Judge Result