C国有n个城市，城市间通过一个树形结构形成一个连通图。城市编号为1到n，其中1号城市为首都。国家有m支军队，分别守卫一条路径的城市。具体来说，对于军队i，他守卫的城市区域可以由一对二元组(xi,yi)代表。表示对于所有在xi到yi的最短路径上的城市，军队i都会守卫他们。
现在有q个重要人物。对于一个重要人物j，他要从他的辖区vj出发，去到首都。出于某些原因，他希望找到一个离首都最近的，且在vj到首都路径上的城市uj，使得至少有kj支军队，能够全程保护他从vj到uj上所经过的所有城市。换句话说，至少有ki支军队，满足在树上，xi到yi的路径能完全覆盖掉vj到uj的路径。
貌似主席树维护$DFS$序这种题目用线段树合并都可以搞，好像本质上都是按照$DFS$序建树
首先把一条覆盖路径拆成两点到$LCA$的两条路径（套路）
然后我们二分这个最小深度，可以发现，如果子树内的路径端点大于二分深度的个数大于等于$k$，那么该深度就合法
然后子树的的信息显然可以用线段树合并维护，二分过程也可以用线段树二分实现
总复杂度$(nlogn)$
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#define M 200010
#define ls ch[node][0]
#define rs ch[node][1]
using namespace std;
vector<int>S[M],Q[M];
int n,m,num,cnt,q;
int head[M],deep[M],ans[M],a[M],f[M],sz[M],son[M],top[M],rt[M];
int val[M<<],ch[M<<][];
struct point{int to,next;}e[M<<];
void add(int from,int to) {
e[++num].next=head[from];
e[num].to=to;
head[from]=num;
}
void dfs1(int x) {
deep[x]=deep[f[x]]+,sz[x]=;
for(int i=head[x];i;i=e[i].next) {
int to=e[i].to;
if(to==f[x]) continue;
f[to]=x;dfs1(to),sz[x]+=sz[to];
if(sz[son[x]]<sz[to]) son[x]=to;
}
}
void dfs2(int x,int tp) {
top[x]=tp;
if(son[x]) dfs2(son[x],tp);
for(int i=head[x];i;i=e[i].next)
if(e[i].to!=f[x]&&e[i].to!=son[x])
dfs2(e[i].to,e[i].to);
}
int lca(int x,int y) {
while(top[x]!=top[y]) {
if(deep[top[x]]<deep[top[y]]) swap(x,y);
x=f[top[x]];
}
return deep[x]<deep[y]?x:y;
}
void insert(int &node,int l,int r,int x,int v) {
if(!node) node=++cnt;val[node]+=v;
if(l==r) return;
int mid=(l+r)/;
if(x<=mid) insert(ls,l,mid,x,v);
else insert(rs,mid+,r,x,v);
}
int query(int node,int l,int r,int d) {
if(val[node]<d) return -;
if(l==r) return l;
int mid=(l+r)/;
if(d<=val[ls]) return query(ls,l,mid,d);
else return query(rs,mid+,r,d-val[ls]);
}
int merge(int x,int y,int l,int r) {
if(!x||!y) return x+y;
int node=++cnt;
if(l==r) {
val[node]=val[x]+val[y];
return node;
}
int mid=(l+r)/;
ls=merge(ch[x][],ch[y][],l,mid);
rs=merge(ch[x][],ch[y][],mid+,r);
val[node]=val[ls]+val[rs];
return node;
}
void dfs(int x,int fa) {
for(int i=;i<S[x].size();i++)
insert(rt[x],,n,S[x][i],);
for(int i=head[x];i;i=e[i].next)
if(e[i].to!=fa)
dfs(e[i].to,x);
for(int i=head[x];i;i=e[i].next)
if(e[i].to!=fa)
rt[x]=merge(rt[x],rt[e[i].to],,n);
for(int i=;i<Q[x].size();i++) {
int id=Q[x][i],u=a[id];
int res=query(rt[x],,n,u);
if(res==-||res>deep[x]) ans[id]=;
else ans[id]=deep[x]-res;
}
}
int main() {
scanf("%d%d",&n,&m);
for(int i=;i<n;i++) {
int x,y;scanf("%d%d",&x,&y);
add(x,y),add(y,x);
}
dfs1(),dfs2(,);
for(int i=;i<=m;i++) {
int x,y;scanf("%d%d",&x,&y);
int LCA=lca(x,y);
if(x!=LCA) S[x].push_back(deep[LCA]);
if(y!=LCA) S[y].push_back(deep[LCA]);
}
scanf("%d",&q);
for(int i=;i<=q;i++) {
int x,y;scanf("%d%d",&x,&y);
a[i]=y;Q[x].push_back(i);
}
dfs(,);
for(int i=;i<=q;i++) printf("%d\n",ans[i]);
return ;
}