链接：https://www.nowcoder.com/acm/contest/172/C
来源：牛客网
题目描述
C国有n个城市，城市间通过一个树形结构形成一个连通图。城市编号为1到n，其中1号城市为首都。国家有m支军队，分别守卫一条路径的城市。具体来说，对于军队i，他守卫的城市区域可以由一对二元组(x,y)代表。表示对于所有在x到y的最短路径上的城市，军队i都会守卫他们。
现在有q个重要人物。对于一个重要人物j，他要从他的辖区v出发，去到首都。出于某些原因，他希望找到一个离首都最近的，且在v到首都路径上的城市u，使得至少有k支军队，能够全程保护他从v到u上所经过的所有城市。换句话说，至少有k支军队，满足在树上，x到y的路径能完全覆盖掉v到u的路径。
输入描述:
第一行输入两个数n,m。
接下来n-1行，每行两个整数u,v,表示存在一条从城市u到城市v的道路。
接下来m行，每行两个整数x,y。描述一个军队的守卫区域。
接下来一行一个整数q。
接下来q行，每行两个整数v,k。
输出描述:
对于每次询问，输出从v
到u
最少需要经过多少条边。假如不存在这样的u
，则输出0。
示例1
输入
8 8
7 1
1 3
3 4
4 6
6 2
4 5
7 8
7 2
7 1
7 1
7 5
1 1
1 3
1 6
5 1
8
5 1
2 1
2 1
4 2
3 2
4 2
1 1
4 1
输出
3
4
4
2
1
2
0
2
备注:
20%: n,m,q <= 300
40%: n,m,q <= 2000
60%: n,m,q <= 50000
100%: n,m,q <= 200000
题目给你一堆点对(X,Y)，并且让你求出对于另外的给定点u，保证有k条路径完全覆盖(u,v)的v的最小深度。
我们考虑把(x,y)分为(x,p), (y,p)， p为x和y的lca。
那么(u,v)被(x,y)覆盖其实就是(u,v)被(x,p)或者(y,p)覆盖。
这里我们只考虑被(x,p)覆盖。
那么肯定是x在u的子树中，p在v的子树之外。
我们对于每一个节点开一棵权值线段树，在x的线段树上的dep[p]位置+1，代表(x,p)有一条路径。
那么我们要(u,v)被(x,p)覆盖，只需要查询u的子树中的线段树是否有<=dep[v]的标记。
如果有那么就成立。
我们要找(u,v)被大于等于k条路径完全覆盖，很容易的想到区间第k小，我们只要在u的子树中的线段树上查询最小的k的存在标记的位置，就是v的深度。
此题完美解决。
(我太菜了考试的时候没想出来)。
所以重复一遍步骤 ：
1.在每个节点开一棵权值线段树，然后对于每个(x,y)在x,y的线段树上分别在dep[lca(x,y)]的位置上+1.
2.dfs一遍合并一个节点儿子的所有子树的线段树。
3.对于每个询问，查询u的线段树中的第k小的位置记为e，答案就是dep[p]-e。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
#define reg register
inline int read() {
int res = ;char ch=getchar();bool fu=;
while(!isdigit(ch)) {if(ch=='-')fu=;ch=getchar();}
while(isdigit(ch)) res=(res<<)+(res<<)+(ch^), ch=getchar();
return fu?-res:res;
}
#define N 200005
int n, m;
struct edge {
int nxt, to;
}ed[N*];
int head[N], cnt;
inline void add(int x, int y) {
ed[++cnt] = (edge){head[x], y};
head[x] = cnt;
} int dep[N];
int ff[N][];
inline void bfs()
{
dep[] = ;
dep[] = -;
queue <int> q;
q.push();
while(!q.empty())
{
int x = q.front();q.pop();
for (reg int i = head[x] ; i ; i = ed[i].nxt)
{
int to = ed[i].to;
if (dep[to]) continue;
dep[to] = dep[x] + ;
ff[to][] = x;
for (reg int j = ; j <= ; j ++)
ff[to][j] = ff[ff[to][j-]][j-];
q.push(to);
}
}
} inline int lca(int x, int y)
{
if (dep[x] < dep[y]) swap(x, y);
for (reg int i = ; i >= ; i --)
if (dep[ff[x][i]] >= dep[y]) x = ff[x][i];
if (x == y) return x;
for (reg int i = ; i >= ; i --)
if (ff[x][i] != ff[y][i]) x = ff[x][i], y = ff[y][i];
return ff[x][];
} int ls[N*], rs[N*], tr[N*], tot;
int root[N*]; int Insert(int l, int r, int o, int p)
{
if (!o) o = ++tot;
tr[o]++;
if (l == r) return o;
int mid = l + r >> ;
if (p <= mid) ls[o] = Insert(l, mid, ls[o], p);
else rs[o] = Insert(mid + , r, rs[o], p);
return o;
} int Merge(int l, int r, int a, int b)
{
if (a * b == ) return a + b;
int node = ++tot;
tr[node] = tr[a] + tr[b];
if (l == r) return node;
int mid = l + r >> ;
ls[node] = Merge(l, mid, ls[a], ls[b]);
rs[node] = Merge(mid + , r, rs[a], rs[b]);
return node;
} void dfs(int x, int fa)
{
for (reg int i = head[x] ; i ; i = ed[i].nxt)
{
int to = ed[i].to;
if (to == fa) continue;
dfs(to, x);
root[x] = Merge(, n, root[x], root[to]);
}
} int K_th(int l, int r, int o, int k)
{
if (tr[o] < k) return 1e9;
if (l == r) return l;
int mid = l + r >> ;
if (tr[ls[o]] >= k) return K_th(l, mid, ls[o], k);
else return K_th(mid + , r, rs[o], k - tr[ls[o]]);
} int main()
{
n = read(), m = read();
for (reg int i = ; i < n ; i ++)
{
int x = read(), y = read();
add(x, y), add(y, x);
}
bfs();
for (reg int i = ; i <= m ; i ++)
{
int x = read(), y = read();
int l = lca(x, y);
root[x] = Insert(, n, root[x], dep[l]);
root[y] = Insert(, n, root[y], dep[l]);
}
dfs(, );
int q = read();
while(q--)
{
int x = read(), k = read();
printf("%d\n", max(, dep[x] - K_th(, n, root[x], k)));
}
return ;
}