题意：
给出一颗N个点的树，树上有M条链，需要满足Q次询问：
每次询问给出两个点(u,v)(u,v)，求从u出发，只通过链来行走（即当前位于某条链的某一个点上，就可以移动到这条链的任意一个点上，这定义为一步），求到达v点的最小步数。链可能会重复覆盖某些点，也可能不连通，若无法到达输出-1
N,Q,M≤105N,Q,M≤105
分析：
首先，有一种很显然的贪心思路：从当前点出发，选取当前能够向目标点走得最远的链，移动到最远点，再继续进行选择。这个贪心思路，在出发点和目标点一定的情况下，可以证明无论是最优性还是合法性，都是最有效的。并且，对于一条有向路径(u,v)，这样的贪心计算出的结果与(v,u)是一致的。
具体证明就不多说了。
然后考虑如何利用这一贪心思路：对于每一次询问，可以广泛地认为是从u点出发，向上走到lca(u,v)，再向下走到v点。换一下方向，可以看作是从u出发，向上走到lca(u,v)，从v出发，向上走到lca(u,v)，但这么考虑就要考虑一个特殊的情况：之前的那种走法，在lca点是不会停留的（即lca有可能是某条链上的中间节点），然而这种考虑方式，会默认在lca处停留。所以要修正一下：
从u出发，到达lca下最近的一个决策点u’，从v出发，到达lca下最近的一个决策点v’，判断是否存在一条链覆盖u’和v’，若存在则答案为(u,u’)+(v,v’)+1，否则为(u,u’)+(v,v’)+2。
对于如何求(u,u’)，我们可以采用倍增算法，对于每个点，将从该点出发，能够到达的深度最小的点（根节点深度为0），设为当前节点的fa[0]，然后更新操作和一般的求lca的操作一模一样，即fa[u][i]=fa[fa[u][i?1]][i?1]fa[u][i]=fa[fa[u][i?1]][i?1]
求解的过程和lca也是一样的。
现在考虑如何判断是否存在一条链覆盖(u’,v’)。
这里推荐官方做法：首先将所有这样的询问存储下来，然后一次dfs查找答案。
不得不承认，出题人dfs的确玩得很骚。
其实就是判断u’,v’的子树中，是否存在同一条链的端点（可以是不同的端点）。
为了判断这个，需要借助dfs序+树状数组。
每次dfs到一个节点，若当前节点存在询问点的左端点，则统计一下右端点的子树中的链的端点总和（利用树状数组+dfn），回溯回来之后，再求一次，看两者之间是否有不同，若存在不同则说明存在一条链覆盖这两个点。
若当前节点为某一链的端点，则将其另一端点加入进树状数组。
看完这两个操作应该能明白了，若两次求出的值不同，则说明在左端点的子树中，存在一条链，其另一端点在右端点子树内。因为全部是加入，没有删除，所以只要和变了，则说明端点的集合改变。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define SF scanf
#define PF printf
#define MAXN 200010
using namespace std;
struct node{int x,y,t,ans;int sum;
}a[MAXN],bus[MAXN];
int n,fa[MAXN][20],dep[MAXN],low[MAXN][20],dfnl[MAXN],dfnr[MAXN],cnt;
vector<int> w[MAXN],busx[MAXN],px[MAXN];
void dfs1(int x){dfnl[x]=++cnt;dep[x]=dep[fa[x][0]]+1;for(int i=1;i<20;i++)fa[x][i]=fa[fa[x][i-1]][i-1];for(int i=0;i<w[x].size();i++)dfs1(w[x][i]);dfnr[x]=cnt;
}
int lca(int x,int y){if(dep[x]<dep[y])swap(x,y);for(int i=19;i>=0;i--)if(dep[fa[x][i]]>=dep[y])x=fa[x][i];if(x==y)return x;for(int i=19;i>=0;i--)if(fa[x][i]!=fa[y][i]){x=fa[x][i];y=fa[y][i];}return fa[x][0];
}
int update(int x,int y){if(dep[x]>dep[y])return y;return x;
}
void dfslow(int x){for(int i=0;i<w[x].size();i++){dfslow(w[x][i]);low[x][0]=update(low[x][0],low[w[x][i]][0]); }
}
pair<int,int> find_low(int x,int y){int res=0;if(dep[low[x][19]]>dep[y])return make_pair(x,-1);for(int i=19;i>=0;i--)if(dep[low[x][i]]>dep[y]){res+=(1<<i);x=low[x][i]; }return make_pair(x,res);
}
int tree[MAXN];
int que(int x){int res=0;while(x>0){res+=tree[x];x-=x&(-x);}return res;
}
int query(int l,int r){return que(r)-que(l-1);
}
void add(int l,int x){while(l<=n){tree[l]+=x;l+=l&(-l);}
}
void dfs(int x){for(int i=0;i<px[x].size();i++){int u=px[x][i];a[u].sum=query(dfnl[a[u].y],dfnr[a[u].y]);}for(int i=0;i<busx[x].size();i++){int u=busx[x][i];if(x==bus[u].x)add(dfnl[bus[u].y],1);elseadd(dfnl[bus[u].x],1);}for(int i=0;i<w[x].size();i++)dfs(w[x][i]);for(int i=0;i<px[x].size();i++){int u=px[x][i];if(a[u].sum==query(dfnl[a[u].y],dfnr[a[u].y]))a[u].ans++;}
}
int main(){int x,m,u,v,q;SF("%d",&n);for(int i=2;i<=n;i++){SF("%d",&x);w[x].push_back(i);fa[i][0]=x;}for(int i=1;i<=n;i++)low[i][0]=i;dep[1]=1;dfs1(1);SF("%d",&m);for(int i=1;i<=m;i++){SF("%d%d",&u,&v);bus[i].x=u,bus[i].y=v;bus[i].t=lca(u,v);low[u][0]=update(low[u][0],bus[i].t);low[v][0]=update(low[v][0],bus[i].t);busx[u].push_back(i);busx[v].push_back(i);}dfslow(1);for(int i=1;i<=n;i++)for(int j=1;j<=19;j++)low[i][j]=low[low[i][j-1]][j-1];SF("%d",&q);for(int i=1;i<=q;i++){a[i].ans=1;SF("%d%d",&u,&v);if(dep[u]<dep[v])swap(u,v);int t=lca(u,v);pair<int,int> res;res=find_low(u,t);if(res.second==-1){a[i].ans=-1;continue; }a[i].x=res.first;a[i].ans+=res.second;if(t==v)continue;res=find_low(v,t);if(res.second==-1){a[i].ans=-1;continue; }a[i].y=res.first;a[i].ans+=res.second;px[a[i].x].push_back(i);}dfs(1);for(int i=1;i<=q;i++)PF("%d\n",a[i].ans);
}