RT t了三个点

#include <bits/stdc++.h>
using namespace std;
const int K = 1000010, M = 100010, N = 500010;
stack<int> stk;
char ss[K], s[10], c[N];
int chg[N];
int val[M], n;
int ls[N], rs[N];

int dfs(int u) {
	//printf("%d\n",u);
	if(u>0 && u<=n) {
		return val[u];
	}
	if(c[u] == '!') {
		return dfs(ls[u])^1;
	} else if(c[u] == '&') {
		int lv = dfs(ls[u]), rv = dfs(rs[u]);
		if(lv == 0) chg[rs[u]] = true;
		if(rv == 0) chg[ls[u]] = true;
		return lv&rv;
	} else { //'|'
		int lv = dfs(ls[u]), rv = dfs(rs[u]);
		if(lv == 1) chg[rs[u]] = true;
		if(rv == 1) chg[ls[u]] = true;
		return lv|rv;
	}
}
//chg[] true:不会影响   false:会影响
void chk(int u, int f) {
	if(u>0&&u<=n)chg[u]|=f;
	f|=chg[u];
	if(ls[u])chk(ls[u],f);
	if(rs[u])chk(rs[u],f);
}
int main() {
	//freopen("p7073.out","w",stdout);
	cin.getline(ss, 1000010);
	scanf("%d", &n);
	for(int i=1; i<=n; ++i) scanf("%d", &val[i]);
	
	int t=n, d=0;
	while(ss[d]) {
		sscanf(ss+d, "%s", s);
		d+=strlen(s)+1;
		//printf("%s\n",s);
		if(s[0] == '!') {
			int v = stk.top(); stk.pop();
			++t; ls[t] = v; c[t] = '!';
			stk.push(t);
		} else if(s[0] == '&') {
			int v1 = stk.top(); stk.pop();
			int v2 = stk.top(); stk.pop();
			++t; ls[t] = v2; rs[t] = v1; c[t] = '&';
			stk.push(t);
		} else if(s[0] == '|') {
			int v1 = stk.top(); stk.pop();
			int v2 = stk.top(); stk.pop();
			++t; ls[t] = v2; rs[t] = v1; c[t] = '|';
			stk.push(t);
		} else { //x__
			int x; sscanf(s+1, "%d", &x);
			stk.push(x);
			//printf("%d\n",x);
		}
	}
	//点 1~n 是变量
	// n+1~t 是符号 
	int ans = dfs(t); //树根
	//printf("val%d\n",val[t]);
	chk(t,0);
	//for(int i=1;i<=t;++i)printf("%d ",chg[i]);
	int q; scanf("%d", &q);
	while(q--) {
		int x; scanf("%d", &x);
		printf("%d\n", ans^(!chg[x]));
	}
	return 0;
}