A5852. 「GXOI / GZOI2019」旧词
编程题
NOI/NOI+/CTSC
知识点
题目描述
> 浮生有梦三千场
> 穷尽千里诗酒荒
> 徒把理想倾倒
> 不如早还乡
>
> 温一壶风尘的酒
> 独饮往事迢迢
> 举杯轻思量
> 泪如潮青丝留他方
>
> <p style="text-align: right; ">——乌糟兽/愚青《旧词》</p>
你已经解决了五个问题，不妨在这大树之下，吟唱旧词一首抒怀。最后的问题就是关于这棵树的，它的描述很简单。
给定一棵 $n$ 个点的有根树，节点标号 $1 \sim n$，$1$ 号节点为根。
给定常数 $k$。
给定 $Q$ 个询问，每次询问给定 $x,y$。
求：
$$\sum\limits_{i \le x} \text{depth}(\text{lca}(i,y))^k$$
$\text{lca}(x,y)$ 表示节点 $x$ 与节点 $y$ 在有根树上的最近公共祖先。
$\text{depth}(x)$ 表示节点 $x$ 的深度，根节点的深度为 $1$。
由于答案可能很大，你只需要输出答案模 $998244353$ 的结果。
> 穷尽千里诗酒荒
> 徒把理想倾倒
> 不如早还乡
>
> 温一壶风尘的酒
> 独饮往事迢迢
> 举杯轻思量
> 泪如潮青丝留他方
>
> <p style="text-align: right; ">——乌糟兽/愚青《旧词》</p>
你已经解决了五个问题，不妨在这大树之下，吟唱旧词一首抒怀。最后的问题就是关于这棵树的，它的描述很简单。
给定一棵 $n$ 个点的有根树，节点标号 $1 \sim n$，$1$ 号节点为根。
给定常数 $k$。
给定 $Q$ 个询问，每次询问给定 $x,y$。
求：
$$\sum\limits_{i \le x} \text{depth}(\text{lca}(i,y))^k$$
$\text{lca}(x,y)$ 表示节点 $x$ 与节点 $y$ 在有根树上的最近公共祖先。
$\text{depth}(x)$ 表示节点 $x$ 的深度，根节点的深度为 $1$。
由于答案可能很大，你只需要输出答案模 $998244353$ 的结果。
输入格式
输入包含 $n+Q$ 行。
第 $1$ 行，三个正整数 $n,Q,k$。
第 $i = 2 \sim n$ 行，每行有一个正整数 $f_i(1 \le f_i \le n)$，表示编号为 $i$ 的节点的父亲节点的编号。
接下来 $Q$ 行，每行两个正整数 $x,y(1 \le x,y \le n)$，表示一次询问。
第 $1$ 行，三个正整数 $n,Q,k$。
第 $i = 2 \sim n$ 行，每行有一个正整数 $f_i(1 \le f_i \le n)$，表示编号为 $i$ 的节点的父亲节点的编号。
接下来 $Q$ 行，每行两个正整数 $x,y(1 \le x,y \le n)$，表示一次询问。
输出格式
输出包含 $Q$ 行，每行一个整数，表示答案模 $998244353$ 的结果。
输入输出样例
输入 #1
5 5 2 1 4 1 2 4 3 5 4 2 5 1 2 3 2
输出 #1
15 11 5 1 6
说明/提示
|测试点编号|$n$ 的规模|$Q$ 的规模|$k$ 的规模|约定|
|:-:|:-:|:-:|:-:|:-:|
|$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$|无|
|:-:|:-:|:-:|:-:|:-:|
|$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$|无|