考虑怎么从弱化版转化过来。
考虑通过树上路径修改和查询更新答案的本质——没错就是差分，我们把单点的信息搞到了一条路径上，那么我们就只要预先处理出每个点的基础贡献，然后就是在弱化版的基础上多乘一个整段区间的基础贡献和就好了。
那么这个单点的基础贡献是什么嘞？很简单，就是 (dep_u ^ k - (dep_u - 1) ^ k)。
然后我们就仿照弱化版搞就是了。
参考代码：
#include <algorithm>
#include <cstdio>
using namespace std;
const int _ = 1e5 + 5, mod = 998244353;
int power(int x, int k) {
int res = 1;
for (; k; k >>= 1, x = 1ll * x * x % mod)
if (k & 1) res = 1ll * res * x % mod;
return res % mod;
}
template < class T > void read(T& s) {
s = 0; int f = 0; char c = getchar();
while ('0' > c || c > '9') f |= c == '-', c = getchar();
while ('0' <= c && c <= '9') s = s * 10 + c - 48, c = getchar();
s = f ? -s : s;
}
int tot, head[_]; struct Edge { int v, nxt; } edge[_ << 1];
void Add_edge(int u, int v) { edge[++tot] = (Edge) { v, head[u] }, head[u] = tot; }
int n, q, k, pw[_], ans[_];
struct node { int x, y, id; } t[_ << 1];
int cmp(node a, node b) { return a.x < b.x; }
int dep[_], siz[_], son[_], dfn[_], rdf[_], top[_], fa[_], sum[_ << 2], tag[_ << 2], a[_ << 2];
int lc(int p) { return p << 1; }
int rc(int p) { return p << 1 | 1; }
void pushup(int p) { sum[p] = (sum[lc(p)] + sum[rc(p)]) % mod; }
void add(int p, int v, int l, int r) {
sum[p] = (sum[p] + 1ll * v * a[p] % mod) % mod, tag[p] = (tag[p] + v) % mod;
}
void pushdown(int p, int l, int r, int mid) {
if (tag[p]) add(lc(p), tag[p], l, mid), add(rc(p), tag[p], mid + 1, r), tag[p] = 0;
}
void build(int p = 1, int l = 1, int r = n) {
if (l == r) { a[p] = (pw[dep[rdf[l]]] - pw[dep[rdf[l]] - 1] + mod) % mod; return ; }
int mid = (l + r) >> 1;
build(lc(p), l, mid), build(rc(p), mid + 1, r), a[p] = (a[lc(p)] + a[rc(p)]) % mod;
}
void update(int ql, int qr, int v, int p = 1, int l = 1, int r = n) {
if (ql <= l && r <= qr) return add(p, v, l, r);
int mid = (l + r) >> 1;
pushdown(p, l, r, mid);
if (ql <= mid) update(ql, qr, v, lc(p), l, mid);
if (qr > mid) update(ql, qr, v, rc(p), mid + 1, r);
pushup(p);
}
int query(int ql, int qr, int p = 1, int l = 1, int r = n) {
if (ql <= l && r <= qr) return sum[p];
int mid = (l + r) >> 1, res = 0;
pushdown(p, l, r, mid);
if (ql <= mid) res = (res + query(ql, qr, lc(p), l, mid)) % mod;
if (qr > mid) res = (res + query(ql, qr, rc(p), mid + 1, r)) % mod;
return res;
}
void dfs(int u, int f) {
dep[u] = dep[f] + 1, siz[u] = 1, fa[u] = f;
for (int i = head[u]; i; i = edge[i].nxt) {
int v = edge[i].v; if (v == f) continue ;
dfs(v, u), siz[u] += siz[v];
if (siz[son[u]] < siz[v]) son[u] = v;
}
}
void dfs(int u, int f, int topf) {
top[rdf[dfn[u] = ++dfn[0]] = u] = topf;
if (son[u]) dfs(son[u], u, topf);
for (int i = head[u]; i; i = edge[i].nxt) {
int v = edge[i].v; if (v == f || v == son[u]) continue ;
dfs(v, u, v);
}
}
void Update(int x) {
int fx = top[x];
while (fx != 1)
update(dfn[fx], dfn[x], 1), x = fa[fx], fx = top[x];
update(1, dfn[x], 1);
}
int Query(int x) {
int fx = top[x], res = 0;
while (fx != 1)
res = (res + query(dfn[fx], dfn[x])) % mod, x = fa[fx], fx = top[x];
return (res + query(1, dfn[x])) % mod;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("cpp.in", "r", stdin), freopen("cpp.out", "w", stdout);
#endif
read(n), read(q), read(k);
for (int i = 1; i <= n; ++i) pw[i] = power(i, k);
for (int x, i = 2; i <= n; ++i) read(x), Add_edge(x, i);
dfs(1, 0), dfs(1, 0, 1), build();
for (int x, y, i = 1; i <= q; ++i)
read(x), read(y), t[i] = (node) { x, y, i };
sort(t + 1, t + q + 1, cmp);
int p = 0;
for (int i = 1; i <= q; ++i) {
while (p < t[i].x) Update(++p);
ans[t[i].id] = (ans[t[i].id] + Query(t[i].y) + mod) % mod;
}
for (int i = 1; i <= q; ++i) printf("%d
", ans[i]);
return 0;
}