这个题基本是个省选难度
但是现在NOIP越来越毒瘤，搞不好出这样的题（小凯：你是不是看不起我）
------------
首先，对于每一个询问$u$，我们找到它的一个祖先，记为$p$
这一条路至少要被$k$条给定路径完全覆盖
其实相当于查询在给定的$m$个$x,y$中，有多少个满足
**$x$在$u$的子树中，$y$在$p$的其他子树中或$p$的子树以外**
反过来也可以
设$z$为$lca(x,y)$，则路径被划分为$(x,z)$和$(z,y)$
只需要$(u,p)$被其中一个覆盖即可
只考虑在$x$的子树中的情况
在$x$处放一个$dep[p]$的标记
这样就只需要查询在$u$的子树中有多少标记小于等于$dep[p]$的
可以动态开点线段树，$dfs$合并子树信息
查询时可以在线段树上二分，相当于找第$k$小数
```
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define reg register
using namespace std;
const int N=2e5+5,inf=1e7;
struct node
{
int to,nxt;
}edge[N<<1];
int n,m,T,num,head[N],f[N][20],dep[N],rt[N];
int cnt,sum[N*80],ls[N*80],rs[N*80];
inline int read()
{
int x=0,w=1;
char c=getchar();
while (!isdigit(c)&&c!='-') c=getchar();
if (c=='-') c=getchar(),w=-1;
while (isdigit(c))
{
x=(x<<1)+(x<<3)+c-'0';
c=getchar();
}
return x*w;
}
inline void add_edge(int from,int to)
{
edge[++num]=(node){to,head[from]};
head[from]=num;
}
void dfs(int k,int fa)
{
f[k][0]=fa; dep[k]=dep[fa]+1;
for (reg int i=1;i<=19;i++) f[k][i]=f[f[k][i-1]][i-1];
for (reg int i=head[k];i;i=edge[i].nxt)
{
int v=edge[i].to;
if (v!=fa) dfs(v,k);
}
}
inline int getlca(int x,int y)
{
if (dep[x]<dep[y]) swap(x,y);
for (reg int i=19;~i;i--)
if (dep[f[x][i]]>=dep[y]) x=f[x][i];
if (x==y) return x;
for (reg int i=19;~i;i--)
if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
return f[x][0];
}
void insert(int &now,int l,int r,int x)
{
if (!now) now=++cnt; ++sum[now];
if (l==r) return; int mid=(l+r)>>1;
if (x<=mid) insert(ls[now],l,mid,x);
else insert(rs[now],mid+1,r,x);
}
int query(int now,int l,int r,int x)
{
if (sum[now]<x) return inf;
if (l==r) return l; int mid=(l+r)>>1;
if (x<=sum[ls[now]]) return query(ls[now],l,mid,x);
return query(rs[now],mid+1,r,x-sum[ls[now]]);
}
int merge(int a,int b,int l,int r)
{
if (!a||!b) return a+b; int now;
sum[now=++cnt]=sum[a]+sum[b];
if (l==r) return now; int mid=(l+r)>>1;
ls[now]=merge(ls[a],ls[b],l,mid);
rs[now]=merge(rs[a],rs[b],mid+1,r);
return now;
}
void dfs1(int k,int fa)
{
for (reg int i=head[k];i;i=edge[i].nxt)
{
int v=edge[i].to;
if (v==fa) continue; dfs1(v,k);
rt[k]=merge(rt[k],rt[v],1,n);
}
}
int main()
{
n=read(),m=read();
for (reg int i=1;i<n;i++)
{
int x=read(),y=read();
add_edge(x,y); add_edge(y,x);
}
dfs(1,0);
for (reg int i=1;i<=m;i++)
{
int x=read(),y=read(),z=getlca(x,y);
insert(rt[x],1,n,dep[z]); insert(rt[y],1,n,dep[z]);
}
dfs1(1,0); T=read();
for (reg int i=1;i<=T;i++)
{
int x=read(),k=read();
printf("%d\n",max(0,dep[x]-query(rt[x],1,n,k)));
}
return 0;
}
```