个人用的是记忆化搜索
昨晚老师考试的时候考到了这道题
同学也都看不出来我的错误

#include<bits/stdc++.h>
using namespace std;
#define OPEN(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
const int M=1.2e6+5,N=1e5+5;
bool Nai;
char s[M];
int A[M],sign[M],val[M],fa[M],frd[M],tot,n,m;
int ans[M][2],stk[M],top;
int dfs(int u,int x)
{
	if(u==m)return x;
	int &res=ans[u][x];
	if(~res)return res;
	if(sign[u]==-3)res=dfs(fa[u],!x);
	else if(sign[u]==-2)res=dfs(fa[u],x|val[frd[u]]);
	else res=dfs(fa[u],x&val[frd[u]]);
	return res;
}
bool Ri;
int main()
{
//	cerr<<(&Ri-&Nai)/1024./1024<<endl;
//	OPEN("expr");
	gets(s+1);
	int len=strlen(s+1);
	memset(ans,-1,sizeof ans);
	for(int i=1;i<=len;++i)
	{
		if(s[i]==' ')continue;
		if(s[i]=='x')
		{
			int res=0; 
			for(++i;isdigit(s[i]);++i)
				res=(res<<1)+(res<<3)+(s[i]^48);
			A[++tot]=res;
		}
		else if(s[i]=='&')A[++tot]=-1;
		else if(s[i]=='|')A[++tot]=-2;
		else A[++tot]=-3;
	}
	scanf("%d",&n);m=n;
	for(int i=1;i<=n;++i)
		scanf("%d",&val[i]);
	for(int i=1;i<=tot;++i)
	{
		if(A[i]>0)stk[++top]=A[i];
		else
		{
			if(A[i]==-3)
			{
				int p=stk[top--];
				stk[++top]=++m;
				val[fa[p]=m]=!val[p];
				sign[p]=A[i];
			}
			else
			{
				int p1=stk[top--];
				int p2=stk[top--];
				frd[p2]=p1;
				frd[p1]=p2;
				stk[++top]=++m;
				fa[p1]=fa[p2]=m;
				sign[p1]=sign[p2]=A[i];
				if(A[i]==-1)val[m]=val[p1]&val[p2];
				else val[m]=val[p1]|val[p2];
			}
		}
	}
	for(int i=1;i<=m;++i)
		ans[i][val[i]]=val[stk[1]];
	int Q;cin>>Q;
	for(int i=1,u;i<=Q;++i)
	{
		scanf("%d",&u);
		printf("%d\n",dfs(u,!val[u]));
	}
	
}

把输出改成

printf("%d\n",!dfs(u,!val[u]));

就能AC,但是过不了样例和大样例
(但是计蒜客的数据不用加!也能过)