思路

首先有一个做法，每次将深度最大的一层的点拉出来问，这样子每次可以删掉一层，但是这太垃圾了，考虑将层数模 $3$ 分类，每次取出点最多的拉出来问，每次询问要把之前确定的边的影响去除，对于一个点 $u$ 若传送后仍在 $u$ 上，此时可以确定 $u$ 所有临边的方向，若不在，先看是否往儿子走了，若都不在儿子上则一定往父亲走了，一次至少去掉当前边的 $\frac{1}{3}$，所以 $30$ 次够了。

代码

#include<bits/stdc++.h>
using namespace std;
vector<int>Query(vector<int>x,vector<int>y);
void Answer(vector<int>a);
int f[100010],id[100010],dep[100010],vis[100010],ans[100010];vector<array<int,2>>e[100010];vector<int>D[100010];
void Solve(int n,vector<int>A,vector<int>B){
    for(int i=0;i<n-1;i++) A[i]++,B[i]++;for(int i=0;i<n-1;i++) e[A[i]].push_back({B[i],i}),e[B[i]].push_back({A[i],i});
    function<void(int,int)>dfs=[&](int u,int fa){
        f[u]=fa;D[(dep[u]=dep[fa]+1)%3].push_back(u);
        for(auto v:e[u]) if(v[0]^fa){id[v[0]]=v[1];dfs(v[0],u);}
    };dfs(1,0);
    for(;;){
        vector<int>cnt(3);for(int i=1;i<=n;i++){
            bool flg=0;for(auto j:e[i]) if(!vis[j[1]]) flg=1;
            if(flg) cnt[dep[i]%3]++;
        }int o=max_element(cnt.begin(),cnt.end())-cnt.begin();if(!cnt[o]) break;
        vector<int>x(n-1),y(n);for(auto i:D[o]){
            y[i-1]=1;
            for(auto j:e[i]) if(vis[j[1]]&&i==(ans[j[1]]?B[j[1]]:A[j[1]])) x[j[1]]=1;
        }auto res=Query(x,y);
        for(auto i:D[o]){
            if(res[i-1]){for(auto j:e[i]) if(!vis[j[1]]) vis[j[1]]=1,ans[j[1]]=(i==A[j[1]]);}
            else{
                bool flg=0;for(auto j:e[i]) if(!vis[j[1]]&&res[j[0]-1]&&j[0]^f[i]) vis[j[1]]=flg=1,ans[j[1]]=(i==B[j[1]]);
                if(!flg){vis[id[i]]=1;ans[id[i]]=(i==B[id[i]]);}
            }
        }
    }Answer(vector<int>(ans,ans+n-1));
}