Description：

给一棵树和树上的 $n$ 条路经，多组询问从 $u$ 点往根走有至少 $k$ 条路经完全覆盖他最远能走到哪里。

$1\le n \le 200000$

Solution：

线段树合并不难想到，但是思路很神奇，首先由于是从某个点往根走，可以把给出的所有路径拆成 $(x,lca)$ 和 $(y,lca)$ ，一定只会有一个有用，设其为 $(x,p)$ ，那么我们要找的 $(u,q)$ 其实就是最高到多少都有 $k$ 条路经满足 $x$ 在 $u$ 的子树中， $p$ 在 $q$ 的上面，那么就在 $x$ 的位置放一个 $dep[p]$ 的标记，这些标记用线段树维护，把所有询问离线下来，然后 $dfs$ 整棵树，在 $dfs$ 的时候把子节点的线段树合并到这个点上，然后在这个点的线段树上找第 $k$ 大就是答案。由于线段树合并时会破坏原线段树结构，所以把询问离线在这个点的线段树合并完成时统一处理。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<vector> 

#include<cstring>

using namespace std;

inline int read()

{

	register int res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

int n,m,q;

#define MAXN 200010

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

inline void add(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;

}

int dep[MAXN],fa[MAXN],siz[MAXN],son[MAXN],top[MAXN];

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)

{

	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] ? a : b);

}

struct node

{

	int lc,rc;

	int tot;

}t[MAXN * 30];

int ptr = 0;

int newnode(){return ++ptr;}

int root[MAXN];

#define mid ((l + r) >> 1)

void ins(int &rt,int p,int l,int r)

{

	if(rt == 0)rt = newnode();

	t[rt].tot += 1;

	if(l == r)return;

	if(p <= mid)ins(t[rt].lc,p,l,mid);

	else ins(t[rt].rc,p,mid + 1,r);

	t[rt].tot = t[t[rt].lc].tot + t[t[rt].rc].tot;

	return;

}

int query(int rt,int k,int l,int r)

{

	if(l == r)return l;

	int s = (t[rt].lc != 0 ? t[t[rt].lc].tot : 0);

	if(k > s)return query(t[rt].rc,k - s,mid + 1,r);

	else return query(t[rt].lc,k,l,mid);

}

int merge(int x,int y)

{

	if(!x)return y;if(!y)return x;

	t[x].tot += t[y].tot;

	t[x].lc = merge(t[x].lc,t[y].lc);

	t[x].rc = merge(t[x].rc,t[y].rc);

	return x;

}

bool vis[MAXN];

vector< pair<int,int> > v[MAXN];

int ans[MAXN];

void dfs(int k)

{

	vis[k] = true;

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

	{

		if(vis[e[i].to])continue;

		dfs(e[i].to);

		root[k] = merge(root[k],root[e[i].to]);

	}

	for(vector< pair<int,int> >::iterator i = v[k].begin();i != v[k].end();++i)

		ans[i -> first] = max(dep[k] - query(root[k],i -> second,1,n),0);

	return;

}

int main()

{

	scanf("%d%d",&n,&m);

	int a,b;

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

	{

		a = read();b = read();

		add(a,b);

	}

	dfs1(1,1);dfs2(1,1);

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

	{

		a = read();b = read();

		int lca = LCA(a,b);

		ins(root[a],dep[lca],1,n);

		ins(root[b],dep[lca],1,n);

	}

	scanf("%d",&q);

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

	{

		a = read();b = read();

		v[a].push_back(make_pair(i,b));

	}

	dfs(1);

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

	{

		printf("%d\n",ans[i]);

	}

	return 0;

}