loj#P3088. 「GXOI / GZOI2019」旧词

「GXOI / GZOI2019」旧词

题目描述

浮生有梦三千场
穷尽千里诗酒荒
徒把理想倾倒
不如早还乡

温一壶风尘的酒
独饮往事迢迢
举杯轻思量
泪如潮青丝留他方

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

你已经解决了五个问题,不妨在这大树之下,吟唱旧词一首抒怀。最后的问题就是关于这棵树的,它的描述很简单。

给定一棵 nn 个点的有根树,节点标号 1n1 \sim n11 号节点为根。
给定常数 kk
给定 QQ 个询问,每次询问给定 x,yx,y
求:

$$\sum\limits_{i \le x} \text{depth}(\text{lca}(i,y))^k $$

lca(x,y)\text{lca}(x,y) 表示节点 xx 与节点 yy 在有根树上的最近公共祖先。
depth(x)\text{depth}(x) 表示节点 xx 的深度,根节点的深度为 11
由于答案可能很大,你只需要输出答案模 998244353998244353 的结果。

输入格式

输入包含 n+Qn+Q 行。
11 行,三个正整数 n,Q,kn,Q,k
i=2ni = 2 \sim n 行,每行有一个正整数 fi(1fin)f_i(1 \le f_i \le n),表示编号为 ii 的节点的父亲节点的编号。
接下来 QQ 行,每行两个正整数 x,y(1x,yn)x,y(1 \le x,y \le n),表示一次询问。

输出格式

输出包含 QQ 行,每行一个整数,表示答案模 998244353998244353 的结果。

5 5 2
1
4
1
2
4 3
5 4
2 5
1 2
3 2
15
11
5
1
6

数据范围与提示

测试点编号 nn 的规模 QQ 的规模 kk 的规模 约定
11 n2,000n \le 2,000 Q2,000Q \le 2,000 1k1091 \le k \le 10^9
22
33
44
55 n50,000n \le 50,000 Q50,000Q \le 50,000 存在某个点,其深度为 nn
66
77
88
99 Q=nQ = n 对于第 ii 个询问,有 x=ix = i
1010
1111 Q50,000Q \le 50,000 k=1k = 1
1212
1313 k=2k = 2
1414
1515 k=3k = 3
1616
1717 1k1091 \le k \le 10^9
1818
1919
2020