代码：（可能有亿点点长）

#include<bits/stdc++.h>
using namespace std;
#define qwq ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
const int N = 1000010;
int n, m;
char str[N];
int w[N];
int h[N], e[N], ne[N], idx = 0;
char c[N];
int stk[N], tt;
bool st[N];

void add(int k, int x)
{
	e[idx] = x;
	ne[idx] = h[k];
	h[k] = idx;
	++ idx;
}

int dfs1(int u)
{
	if (u <= n)
		return w[u];
	if (c[u] == '!')
		return w[u] = !dfs1(e[h[u]]);
	else if (c[u] == '&')
	{
		w[u] = 1;
		for (int i = h[u]; ~i; i = ne[i])
		{
			w[u] &= dfs1(e[i]);
		}
		return w[u];
	}
	else
	{
		w[u] = 0;
		for (int i = h[u]; ~i; i = ne[i])
		{
			w[u] |= dfs1(e[i]);
		}
		return w[u];
	}
}

void dfs2(int u)
{
	st[u] = 1;
	if (u <= n)
		return;
	if (c[u] == '!')
		dfs2(e[h[u]]);
	else
	{
		int a = e[h[u]], b = e[ne[h[u]]];
		if (c[u] == '&')
		{
			if (w[a])
				dfs2(b);
			if (w[b])
				dfs2(a);
		}
		else
		{
			if (!w[a])
				dfs2(b);
			if (!w[b])
				dfs2(a);
		}
	}
}

int main()
{
    qwq;
    cin.getline(str, N);
    cin >> n;
    for (int i = 1; i <= n; ++ i)
    {
    	cin >> w[i];
	}
	memset(h, -1, sizeof(h));
	m = n;
	for (int i = 0; str[i]; ++ i)
	{
		if (str[i] == 'x')
		{
			int k = 0;
			++ i;
			while (str[i] >= '0' && str[i] <= '9')
				k = k * 10 + str[i] - '0', ++ i;
			stk[++ tt] = k;
		}
		else if (str[i] == '!')
		{
			c[++ m] = str[i];
			add(m, stk[tt --]);
			stk[++ tt] = m;
			++ i;
		}
		else
		{
			c[++ m] = str[i];
			add(m, stk[tt --]);
			add(m, stk[tt --]);
			stk[++ tt] = m;
			++ i;
		}
	}
	int root = stk[tt];
	int res = dfs1(root);
	dfs2(root);
	int q;
	cin >> q;
	while (-- q)
	{
		int x;
		cin >> x;
		if (st[x])
			cout << !res << endl;
		else
			cout << res << endl;
	}
    return 0;
}
``~