树链剖分求lca
#include<bits/stdc++.h>
using namespace std;
const int N=201000;
int ne[N],head[N],ver[N],idx;
int top[N],son[N],sz[N],dep[N],fa[N];
int root;
int n,m;
void add(int u,int v)
{
ne[idx]=head[u];
ver[idx]=v;
head[u]=idx;
idx++;
}
inline void dfs1(int u,int father,int depth)
{
fa[u]=father;
sz[u]=1;
dep[u]=depth;
for(int i=head[u];i!=-1;i=ne[i])
{
int j=ver[i];
if(j==father)continue;
dfs1(j,u,depth+1);
sz[u]+=sz[j];
if(sz[son[u]]<sz[j]) son[u]=j;
}
}
inline void dfs2(int u,int t)
{
top[u]=t;
if(!son[u])return ;
dfs2(son[u],t);
for(int i=head[u];i!=-1;i=ne[i])
{
int j=ver[i];
if(j==fa[u]||j==son[u]) continue;
dfs2(j,j);
}
}
int lca(int u,int v)
{
while(top[u]!=top[v])
{
if(dep[top[u]]<dep[top[v]])
swap(u,v);
u=fa[top[u]];
}
if(dep[u]<dep[v]) swap(u,v);
return v;
}
int main()
{
memset(head,-1,sizeof(head));
cin>>n;
for(int i=1;i<=n;i++)
{
int a,b;
cin>>a>>b;
if(b==-1) root=a;
else
{
add(a,b);
add(b,a);
}
}
dfs1(root,0,1);
dfs2(root,root);
cin>>m;
for(int i=1;i<=m;i++)
{
int a,b;
cin>>a>>b;
int lc=lca(a,b);
if(a==lc)cout<<"1"<<endl;
else if(lc==b)cout<<"2"<<endl;
else cout<<"0"<<endl;
}
return 0;
}