「我眼泪之中 背负了所有 在最深处的心情却无法说出口 心中的痛 别离的梦」

# [GXOI/GZOI2019]旧词

### 难度：[NOI/NOI+/CTSC]

题目描述


——乌糟兽/愚青《旧词》

$\text{lca}(x,y)$ 表示节点 $x$ 与节点 $y$ 在有根树上的最近公共祖先。
$\text{depth}(x)$ 表示节点 $x$ 的深度，根节点的深度为 $1$。

## 输入输出样例

5 5 2
1
4
1
2
4 3
5 4
2 5
1 2
3 2

15
11
5
1
6

        说明
### 样例解释


### 数据范围

$1$ $n \le 2,000$ $Q \le 2,000$ $1 \le k \le 10^9$
$2$ $n \le 2,000$ $Q \le 2,000$ $1 \le k \le 10^9$
$3$ $n \le 2,000$ $Q \le 2,000$ $1 \le k \le 10^9$
$4$ $n \le 2,000$ $Q \le 2,000$ $1 \le k \le 10^9$
$5$ $n \le 50,000$ $Q \le 50,000$ $1 \le k \le 10^9$ 存在某个点，其深度为 $n$
$6$ $n \le 50,000$ $Q \le 50,000$ $1 \le k \le 10^9$ 存在某个点，其深度为 $n$
$7$ $n \le 50,000$ $Q \le 50,000$ $1 \le k \le 10^9$ 存在某个点，其深度为 $n$
$8$ $n \le 50,000$ $Q \le 50,000$ $1 \le k \le 10^9$ 存在某个点，其深度为 $n$
$9$ $n \le 50,000$ $Q = n$ $1 \le k \le 10^9$ 对于第 $i$ 个询问，有 $x = i$
$10$ $n \le 50,000$ $Q = n$ $1 \le k \le 10^9$ 对于第 $i$ 个询问，有 $x = i$
$11$ $n \le 50,000$ $Q \le 50,000$ $k = 1$
$12$ $n \le 50,000$ $Q \le 50,000$ $k = 1$
$13$ $n \le 50,000$ $Q \le 50,000$ $k = 2$
$14$ $n \le 50,000$ $Q \le 50,000$ $k = 2$
$15$ $n \le 50,000$ $Q \le 50,000$ $k = 3$
$16$ $n \le 50,000$ $Q \le 50,000$ $k = 3$
$17$ $n \le 50,000$ $Q \le 50,000$ $1 \le k \le 10^9$
$18$ $n \le 50,000$ $Q \le 50,000$ $1 \le k \le 10^9$
$19$ $n \le 50,000$ $Q \le 50,000$ $1 \le k \le 10^9$
$20$ $n \le 50,000$ $Q \le 50,000$ $1 \le k \le 10^9$

## 题解

13，14两个点相当于是$2k-1$的等差数列，也是可以的。

1. 将询问离线按照x排序。
2. 从1~n，每个点加入HPD，方法是将根路径上每个点$x$加上$dep^k(x)$
3. 加完后将$x$等于所加点编号的询问查询处理

1小时轻松获得了本题的思路满分