Description：

给定一棵树和若干条路线，每条路线相当于树上 $x,y$ 之间的路径，途径路径上的每个点。

给出若干个询问，每次询问从 $u$ 到 $v$ 至少需要利用几条路线。

$N,M,Q\le200000$

Solution：

先对每个点倍增求出经过 $2^k$ 条路线能到达的最高点，对于每个询问，先处理出各差一步到达 $LCA$ 所必须乘坐的最小路线数，然后问题就变成了给出树上 $N$ 个路径和 $k$ 个点对，问每个点对是否存在于同一条路径上，如果是，答案 $+1$ ，否则 $+2$ ，将询问离线， $dfs$ 整棵树，对于路径 $(x,y)$ ，在 $dfs$ 到 $x$ 时在 $dfs$ 序上 $y$ 对应位置 $+1$ ，这样只要统计 $a$ 的子树是否使以 $b$ 为根的子树发生变化即可知道 $a$ 到 $b$ 有无路径。注意特判不可达和一个点是另一个点祖先的情况。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m,s;

#define MAXN 200010

#define INF 0x3f3f3f3f

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void addedge(int a,int b)

{

	++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	++edgenum;e[edgenum].to = a;e[edgenum].nxt = lin[b];lin[b] = edgenum;

	return;

}

struct route

{

	int to,nxt;

}r[MAXN << 1];

int rnum = 0;

int rlin[MAXN] = {0};

void radd(int a,int b)

{

	++rnum;r[rnum].to = b;r[rnum].nxt = rlin[a];rlin[a] = rnum;

	++rnum;r[rnum].to = a;r[rnum].nxt = rlin[b];rlin[b] = rnum;

	return;

}

struct query

{

	int to,nxt,ans,temp,tag;

}q[MAXN];

int qnum = 0;

int qlin[MAXN] = {0};

void qadd(int a,int b,int c,int d)

{

	++qnum;q[qnum].to = b;q[qnum].ans = c;q[qnum].tag = d;q[qnum].nxt = qlin[a];qlin[a] = qnum;

	return;

}

int dep[MAXN],siz[MAXN],son[MAXN],fa[MAXN],top[MAXN],rank[MAXN],tot = 0;

void dfs1(int k,int depth)

{

	dep[k] = depth;

	siz[k] = 1;

	for(int i = lin[k];i != 0;i = e[i].nxt)

		if(e[i].to != fa[k])

		{

			fa[e[i].to] = k;

			dfs1(e[i].to,depth + 1);

			siz[k] += siz[e[i].to];

			if(son[k] == 0 || siz[e[i].to] > siz[son[k]])

				son[k] = e[i].to;

		}

	return;

}

void dfs2(int k,int tp)

{

	rank[k] = ++tot;

	top[k] = tp;

	if(son[k] == 0)return;

	dfs2(son[k],tp);

	for(int i = lin[k];i != 0;i = e[i].nxt)

		if(e[i].to != fa[k] && e[i].to != son[k])

			dfs2(e[i].to,e[i].to);

	return;

}

int LCA(int a,int b)

{

	while(top[a] != top[b])

	{

		if(dep[top[a]] < dep[top[b]])swap(a,b);

		a = fa[top[a]];

	}

	return dep[a] > dep[b] ? b : a;

}

int f[MAXN][20];

void getlowest(int k)

{

	int t = -1;

	for(int i = lin[k];i != 0;i = e[i].nxt)

		if(e[i].to != fa[k])

		{

			getlowest(e[i].to);

			if(t == -1 || dep[t] > dep[f[e[i].to][0]])

				t = f[e[i].to][0];

		}

	if(t != -1 && dep[t] < dep[f[k][0]])f[k][0] = t;

	return;

}

int power[20];

int c[MAXN];

int lowbit(int x){return x&(-x);}

void add(int p,int x){for(;p <= n;p += lowbit(p))c[p] += x;return;}

int sum(int p){int res = 0;for(;p >= 1;p -= lowbit(p))res += c[p];return res;}

void dfs(int k)

{

	for(int i = qlin[k];i != 0;i = q[i].nxt)

		if(q[i].tag != -1 && q[i].tag != -2)

			q[i].temp = sum(rank[q[i].to] + siz[q[i].to] - 1) - sum(rank[q[i].to] - 1);

	for(int i = lin[k];i != 0;i = e[i].nxt)

		if(e[i].to != fa[k])

			dfs(e[i].to);

	for(int i = rlin[k];i != 0;i = r[i].nxt)

		add(rank[r[i].to],1);

	for(int i = qlin[k];i != 0;i = q[i].nxt)

		if(q[i].tag != -1 && q[i].tag != -2)

			if(sum(rank[q[i].to] + siz[q[i].to] - 1) - sum(rank[q[i].to] - 1) != q[i].temp)

				q[i].ans += 1;

			else

				q[i].ans += 2;

	return;

}

int main()

{

	scanf("%d",&n);

	int a,b;

	for(int i = 2;i <= n;++i)

	{

		scanf("%d",&a);

		addedge(a,i);

	}

	dfs1(1,1);

	dfs2(1,1);

	scanf("%d",&m);

	for(int i = 1;i <= n;++i)

		f[i][0] = i;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d",&a,&b);

		radd(a,b);

		int k = LCA(a,b);

		if(dep[f[a][0]] > dep[k])

			f[a][0] = k;

		if(dep[f[b][0]] > dep[k])

			f[b][0] = k;

	}

	getlowest(1);

	for(int k = 1;k <= 19;++k)

		for(int i = 1;i <= n;++i)

			f[i][k] = f[f[i][k - 1]][k - 1];

	power[0] = 1;

	for(int i = 1;i <= 19;++i)power[i] = power[i - 1] * 2;

	scanf("%d",&s);

	for(int i = 1;i <= s;++i)

	{

		scanf("%d%d",&a,&b);

		int lca = LCA(a,b);

		int ans1 = 0,ans2 = 0;

		bool found1 = (a == lca),found2 = (b == lca); 

		for(int k = 19;k >= 0;--k)

		{

			if(dep[f[a][k]] <= dep[lca])

				found1 = true;

			if(f[a][k] != -1 && dep[f[a][k]] > dep[lca])

			{

				a = f[a][k];

				ans1 += power[k];

			}

			if(dep[f[b][k]] <= dep[lca])

				found2 = true;

			if(f[b][k] != -1 && dep[f[b][k]] > dep[lca])

			{

				b = f[b][k];

				ans2 += power[k];

			}

		}

		int ans = ans1 + ans2;

		if(a == lca)ans -= ans1;

		if(b == lca)ans -= ans2;

		if(found1 && found2)

			if(a != lca && b != lca)

				qadd(a,b,ans1 + ans2,0);

			else

				qadd(a,b,ans + 1,-1);

		else

			qadd(a,b,-1,-2);

	}

	dfs(1);

	for(int i = 1;i <= qnum;++i)

	{

		cout << q[i].ans << endl;

	}

	return 0;

}