Problem Link

首先一条链可以尝试二分找第一个 OR，即选一个前缀，每个点挂的叶子填 $1$，链下方的点填 $0$，那么可以判断前缀中是否有 OR，找到 OR 后，可以同时翻转该点以及其两个儿子使其变成 AND，然后就能继续二分了。

然后考虑完美二叉树的情况，那么依旧要二分，发现我们可以从上往下对每层的点二分，具体来说之前每层的点已经知道符号，所有可以全部变成 OR，然后这层要检验的每个点一个子树全填 $0$，一个子树全填 $1$，就能判断这些点中有没有 OR。

一般的情况考虑拼合两种构造，我们可以选若干条没有祖先后代关系的链，要求这些点的祖先都已经被确定，此时就能在这个点集上二分了。

具体就是每条链用第一种方法构造，使得有 OR 时链顶为 $1$，然后每个点的所有祖先填 OR 即可。

此时我们把图分成 $k$ 个点集就会使用 $k$ 次额外的询问，注意到取出原树的重链剖分，按到根轻边个数分组恰好满足题意，则交互次数 $R(\log n+1)+\log n$。

注意到瓶颈在第一部分，这种二分求多个物品的问题，一个经典优化就是顶层分块，我们取块长 $2^b$，然后把每个点集拆成若干 $\le 2^b$ 的段，然后每段内部依次二分，则交互次数 $R(b+1)+\log n+\dfrac{n}{2^b}$，取 $b=6$ 可以通过过。

时间复杂度 $\mathcal O(n^2)$。

代码：

#include<bits/stdc++.h>
#include "circuit.h"
using namespace std;
const int MAXN=16005,B=64;
basic_string <int> G[MAXN],ch[MAXN],id[MAXN],E[MAXN];
int n,siz[MAXN],hson[MAXN];
void dfs1(int u) {
	siz[u]=1,hson[u]=n;
	for(int v:G[u]) {
		dfs1(v),siz[u]+=siz[v];
		if(siz[v]>siz[hson[u]]) hson[u]=v;
	}
}
void dfs2(int u,int d) {
	ch[d].push_back(u);
	if(hson[u]<n) dfs2(hson[u],d);
	for(int v:G[u]) if(v^hson[u]) dfs2(v,d+1);
}
string solve(int N,int,vector<int>L,vector<int>R) {
	for(int i=0;i<N;++i) for(int x:{L[i],R[i]}) if(x<N) G[i].push_back(x);
	for(int i=N;i<=2*N;++i) E[i]={i};
	for(int i=N-1;~i;--i) E[i]=E[L[i]]+E[R[i]];
	n=N,dfs1(0),dfs2(0,0);
	int m=0;
	for(int d=0;d<20;++d) if(ch[d].size()) {
		for(int x:ch[d]) {
			id[m].push_back(x);
			if((int)id[m].size()==B) ++m;
		}
		m++;
	}
	string ans=string(n,'&');
	for(int d=0;d<m;++d) if(id[d].size()) {
		string qy=string(2*n+1,'0');
		for(int c=0;c<d;++c) for(int x:id[c]) {
			if(ans[x]=='&') qy[x]^=1,qy[L[x]]^=1,qy[R[x]]^=1;
		}
		auto chk=[&](int x) {
			string t=qy;
			for(int i=0;i<=x;++i) {
				int u=id[d][i];
				if(hson[u]<n) {
					for(int o:E[L[u]^R[u]^hson[u]]) t[o]^=1;
				} else t[L[u]]^=1;
			}
			return query(t);
		};
		int sz=id[d].size()-1,p=-1;
		while(chk(sz)) {
			int x=sz;
			for(int k=1<<15;k;k>>=1) if(x-k>p&&chk(x-k)) x-=k;
			int u=id[d][x]; p=x;
			ans[u]='|',qy[u]^=1,qy[L[u]]^=1,qy[R[u]]^=1;
		}
	}
	return ans;
}