解题思路：倍增+树剖+树状数组
对于每次询问，我们可以看成是两个点都不断往上跳（如果一个点是另一个点的祖先则是只有一个跳），有一个很明显的贪心策略：每次都跳到能跳到的深度最小的点。然而一次一次往上跳可能被极端数据卡掉，所以要用倍增维护跳 \(2^i\) 次能跳到哪里。
然而两个点都跳到他们的 lca 上并不一定是最优方案，所以可以让两个点都跳到差一步能跳到 lca 的位置，然后判断是否有一条路直接联通两个点。对于这个问题，我们可以处理出 dfs 序，将每一条公交车线路看成是坐标系上 \((dfn_u,dfn_v)\) 的一个点，每次询问就是判断左下角是 \((dfn_u,dfn_v)\)，右上角是 \(end_u,end_v\) 的矩形内是否有点，其中 \(end_i\) 表示 \(i\) 的子树中点的 \(dfn\) 的最大值。可以转化成二维偏序问题，用树状数组维护。板子题链接。其中要特判一下一个点是另一个点的祖先的情况，直接跳即可。
求 lca 推荐用树剖，顺便还可以处理出一个 dfn。
code：
点击查看代码
int n,m,q,e[maxn],ans[maxn],res[maxn<<2],fm[maxn][22];
int siz[maxn],dep[maxn],fa[maxn],wt[maxn];
int cnt,top[maxn],dfn[maxn];
int tot,head[maxn];
bool vis[maxn];
struct node{
int to,nxt;
}edge[maxn<<1];
struct zb{
int x,y,id;
bool operator<(const zb &tmp)const{return x<tmp.x;}
}qry[maxn<<2];
std::pii d[maxn<<1];
inline void add(int u,int v){
edge[++tot]={v,head[u]};
head[u]=tot;
}
inline int lowbit(int x){return x&(-x);}
inline void update(int x){
while(x<=n)e[x]++,x+=lowbit(x);
}
inline int query(int x){
int ret=0;
while(x)ret+=e[x],x-=lowbit(x);
return ret;
}
void dfs1(int u,int f){
fa[u]=f;siz[u]=1;
for(int i=head[u];i;i=edge[i].nxt){
int v=edge[i].to;
if(v==f)continue;
dep[v]=dep[u]+1;
dfs1(v,u);
siz[u]+=siz[v];
if(siz[v]>siz[wt[u]])wt[u]=v;
}
}
void dfs2(int u,int t){
top[u]=t;dfn[u]=++cnt;
if(!wt[u])return;
dfs2(wt[u],t);
for(int i=head[u];i;i=edge[i].nxt){
int v=edge[i].to;
if(v==fa[u]||v==wt[u])continue;
dfs2(v,v);
}
}
void dfs3(int u){//处理跳一次能跳到哪里
for(int i=head[u];i;i=edge[i].nxt){
int v=edge[i].to;
if(v==fa[u])continue;
dfs3(v);
if(~fm[v][0])fm[u][0]=dep[fm[v][0]]<dep[fm[u][0]]?fm[v][0]:fm[u][0];
}
if(fm[u][0]==u||!fm[u][0])fm[u][0]=-1;
}
void dfs4(int u){//倍增
for(int i=1;i<=20;i++){
if(~fm[u][i-1])fm[u][i]=fm[fm[u][i-1]][i-1];
else fm[u][i]=-1;
}
for(int i=head[u];i;i=edge[i].nxt){
int v=edge[i].to;
if(v==fa[u])continue;
dfs4(v);
}
}
int get_lca(int u,int v){
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]])swap(u,v);
u=fa[top[u]];
}
return dep[u]<dep[v]?u:v;
}
int get_ans(int u,int v,int k){//两个/一个点往上跳
int w=get_lca(u,v),ret=0;
if(w==u){
for(int i=20;~i;i--){
if(~fm[v][i]&&dep[fm[v][i]]>dep[w])v=fm[v][i],ret+=(1<<i);
}
return ~fm[v][0]?ret+1:-1;
}else if(w==v){
for(int i=20;~i;i--){
if(~fm[u][i]&&dep[fm[u][i]]>dep[w])u=fm[u][i],ret+=(1<<i);
}
return ~fm[u][0]?ret+1:-1;
}else{
for(int i=20;~i;i--){
if(~fm[u][i]&&dep[fm[u][i]]>dep[w])u=fm[u][i],ret+=(1<<i);
}
for(int i=20;~i;i--){
if(~fm[v][i]&&dep[fm[v][i]]>dep[w])v=fm[v][i],ret+=(1<<i);
}
vis[k]=true;
}
int x=dfn[u],y=dfn[v],kk=k<<2;
qry[kk-3]={x+siz[u]-1,y+siz[v]-1,kk-3};qry[kk-2]={x-1,y-1,kk-2};
qry[kk-1]={x+siz[u]-1,y-1,kk-1};qry[kk]={x-1,y+siz[v]-1,kk};
return ~fm[u][0]&&~fm[v][0]||fm[u][0]==v||fm[v][0]==u?ret:-1;
}
void solve(){
read(n);
for(int u=2,v;u<=n;u++){
read(v);
add(u,v);add(v,u);
}
dep[0]=inf;
dfs1(1,0);dfs2(1,1);
read(m);
for(int i=1,u,v;i<=m;i++){
read(u);read(v);
d[(i<<1)-1]=mp(dfn[u],dfn[v]);d[(i<<1)]=mp(dfn[v],dfn[u]);
int w=get_lca(u,v);
fm[u][0]=dep[w]<dep[fm[u][0]]?w:fm[u][0];
fm[v][0]=dep[w]<dep[fm[v][0]]?w:fm[v][0];
}
dfs3(1);dfs4(1);
read(q);
for(int i=1,u,v;i<=q;i++){
read(u);read(v);
ans[i]=get_ans(u,v,i);
}
const int mm=m<<1,qq=q<<2;
sort(d+1,d+mm+1);sort(qry+1,qry+qq+1);
for(int i=1,j=1;i<=qq;i++){
while(j<=mm&&d[j].fi<=qry[i].x)update(d[j++].se);
res[qry[i].id]=query(qry[i].y);
}
for(int i=1;i<=q;i++){
int now=i<<2;
if(vis[i]&&~ans[i]){
if(res[now-3]+res[now-2]-res[now-1]-res[now]==0)ans[i]+=2;
else ans[i]++;
}
write(ans[i]);putchar('\n');
}
}