题解
可以发现每次修改的是这个点往上一条连续的链，如果我要把1改成0，需要满足这一段往上的一部分都有两个1
如果我要把0改成1，需要满足这一段往上的部分有两个0
对于每个点记录1的个数，发现我们只会把一棵树的2全部改成1或者把1全部改成2，这样加标记的时候可以同时维护是否全1或者是否全2，用lct维护，修改的时候access一遍，直接在平衡树上二分即可
代码
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define MAXN 1000005
#define eps 1e-10
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
res = 0;T f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
struct node {
int lc,rc,fa,val,lz;
bool all[2];
}tr[MAXN];
int num[MAXN * 2],N,Q,fa[MAXN * 2],d[2];
vector<int> son[MAXN];
bool isRoot(int u) {
if(!tr[u].fa) return true;
return tr[tr[u].fa].lc != u && tr[tr[u].fa].rc != u;
}
bool which(int u) {
return tr[tr[u].fa].lc == u;
}
void addlz(int u,int v) {
tr[u].val += v;
tr[u].lz += v;
tr[u].all[0] = tr[u].all[1] = 0;
if(v == -1) tr[u].all[0] = 1;
if(v == 1) tr[u].all[1] = 1;
}
void pushdown(int u) {
if(tr[u].lz) {
if(tr[u].lc) addlz(tr[u].lc,tr[u].lz);
if(tr[u].rc) addlz(tr[u].rc,tr[u].lz);
tr[u].lz = 0;
}
}
void update(int u) {
for(int i = 0 ; i <= 1 ; ++i) {
tr[u].all[i] = (tr[u].val == i + 1) & tr[tr[u].lc].all[i] & tr[tr[u].rc].all[i];
}
}
void Rotate(int u) {
int v = tr[u].fa,w = tr[v].fa;
if(!isRoot(v)) {(v == tr[w].lc ? tr[w].lc : tr[w].rc) = u;}
int b = (u == tr[v].lc ? tr[u].rc : tr[u].lc);
tr[u].fa = w;tr[v].fa = u;
if(b) tr[b].fa = v;
if(u == tr[v].lc) {tr[u].rc = v;tr[v].lc = b;}
else {tr[u].lc = v;tr[v].rc = b;}
update(v);
}
void Splay(int u) {
static int que[MAXN],tot;
tot = 0;
int x;
for(x = u ; !isRoot(x) ; x = tr[x].fa) {
que[++tot] = x;
}
que[++tot] = x;
for(int i = tot ; i >= 1 ; --i) {
pushdown(que[i]);
}
while(!isRoot(u)) {
if(!isRoot(tr[u].fa)) {
if(which(tr[u].fa) == which(u)) Rotate(tr[u].fa);
else Rotate(u);
}
Rotate(u);
}
update(u);
}
void Access(int u) {
for(int x = 0 ; u ; x = u, u = tr[u].fa) {
Splay(u);
tr[u].rc = x;
update(u);
}
}
void dfs(int u) {
for(int j = 0 ; j < 3 ; ++j) {
if(son[u][j] <= N) {
dfs(son[u][j]);
tr[u].val += (tr[son[u][j]].val >= 2);
tr[son[u][j]].fa = u;
}
else {
tr[u].val += num[son[u][j] - N];
fa[son[u][j] - N] = u;
}
}
if(tr[u].val == 1) tr[u].all[0] = 1;
if(tr[u].val == 2) tr[u].all[1] = 1;
}
void Init() {
read(N);
int a;
for(int i = 1 ; i <= N ; ++i) {
for(int j = 0 ; j < 3 ; ++j) {
read(a);
son[i].pb(a);
}
}
for(int i = 1 ; i <= 2 * N + 1 ; ++i) read(num[i]);
dfs(1);
}
void Solve() {
read(Q);
int v;
d[0] = 1,d[1] = -1;
tr[0].all[0] = tr[0].all[1] = 1;
while(Q--) {
read(v);v -= N;
Access(fa[v]);
Splay(fa[v]);
if(tr[fa[v]].all[num[v]]) {
addlz(fa[v],d[num[v]]);
}
else {
int p = fa[v],res;
while(1) {
res = p;
pushdown(p);
if(tr[p].rc && !tr[tr[p].rc].all[num[v]]) {p = tr[p].rc;continue;}
if(tr[p].val != num[v] + 1) break;
if(tr[p].lc && !tr[tr[p].lc].all[num[v]]) {p = tr[p].lc;continue;}
break;
}
Splay(res);
if(tr[res].rc) addlz(tr[res].rc,d[num[v]]);
tr[res].val += d[num[v]];
update(res);
}
num[v] ^= 1;
Splay(1);
out(tr[1].val >= 2);enter;
}
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Init();
Solve();
}