rt，从 P4211 过来的。有思路后简单写了写调了调，但是样例调不过

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <cassert>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <cstdlib>
#include <set>
using namespace std;
#define ll long long
#define ull unsigned long long
#define int ll
int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + (ch - '0');
        ch = getchar();
    }
    return x * f;
}
const int MAXN = 1e6 + 10;
const int mod = 998244353;
int n, m, t;
int mi[MAXN];
int quickpow(int a, int b)
{
    int res = 1;
    while (b)
    {
        if (b & 1)
            res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
int head[MAXN], tt = 0;
struct edge
{
    int to, nxt;
} e[MAXN << 1];
void add(int x, int y)
{
    e[++tt].nxt = head[x];
    head[x] = tt;
    e[tt].to = y;
}
struct question
{
    int u, z, id;
    bool operator<(const question b) const
    {
        return u < b.u;
    }
} q[MAXN];
int fa[MAXN], son[MAXN], siz[MAXN], dep[MAXN];
void dfs1(int u, int fat)
{
    fa[u] = fat;
    siz[u] = 1;
    dep[u] = dep[fat] + 1;
    for (int i = head[u]; i; i = e[i].nxt)
    {
        int v = e[i].to;
        if (v == fat)
            continue;
        dfs1(v, u);
        siz[u] += siz[v];
        if (siz[son[u]] < siz[v])
            son[u] = v;
    }
}
int top[MAXN], dfn[MAXN], seg[MAXN], idx = 0;
void dfs2(int u, int topfa)
{
    dfn[u] = ++idx;
    seg[dfn[u]] = idx;
    top[u] = topfa;
    if (son[u])
        dfs2(son[u], topfa);
    for (int i = head[u]; i; i = e[i].nxt)
    {
        int v = e[i].to;
        if (v == fa[u] || v == son[u])
            continue;
        dfs2(v, v);
    }
}
struct tree
{
    int l, r;
    int sum, add;
    int k;
} tr[MAXN << 1];
void pushup(int k)
{
    tr[k].sum = (tr[k << 1].sum + tr[k << 1 | 1].sum) % mod;
}
void build(int k, int l, int r)
{
    tr[k].l = l, tr[k].r = r;
    if (l == r)
    {
        tr[k].k = (mi[dep[seg[l]]] - mi[dep[seg[l]] - 1] + mod) % mod;
        return;
    }
    int mid = l + r >> 1;
    build(k << 1, l, mid), build(k << 1 | 1, mid + 1, r);
    tr[k].k = (tr[k << 1].k + tr[k << 1 | 1].k) % mod;
}
void pushdown(int k)
{
    if (tr[k].add)
    {
        tr[k << 1].sum = (tr[k << 1].sum + tr[k << 1].k * tr[k].add) % mod;
        tr[k << 1 | 1].sum = (tr[k << 1 | 1].sum + tr[k << 1 | 1].k * tr[k].add) % mod;
        tr[k << 1].add = (tr[k << 1].add + tr[k].add) % mod;
        tr[k << 1 | 1].add = (tr[k << 1 | 1].add + tr[k].add) % mod;
        tr[k].add = 0;
    }
}
void modefy1(int k, int l, int r)
{
    if (l <= tr[k].l && tr[k].r <= r)
    {
        tr[k].add++;
        tr[k].sum = (tr[k].sum + tr[k].k) % mod;
        return;
    }
    pushdown(k);
    int mid = tr[k].l + tr[k].r >> 1;
    if (l <= mid)
        modefy1(k << 1, l, r);
    if (r > mid)
        modefy1(k << 1 | 1, l, r);
    pushdown(k << 1), pushdown(k << 1 | 1);
    pushup(k);
}
int query1(int k, int l, int r)
{
    pushdown(k);
    if (l <= tr[k].l && tr[k].r <= r)
        return tr[k].sum;
    pushdown(k);
    int res = 0;
    int mid = tr[k].l + tr[k].r >> 1;
    if (l <= mid)
        res = (res + query1(k << 1, l, r)) % mod;
    if (r > mid)
        res = (res + query1(k << 1 | 1, l, r)) % mod;
    pushup(k);
    return res;
}
void modefy(int x)
{
    while (top[x])
    {
        modefy1(1, dfn[top[x]], dfn[x]);
        x = fa[top[x]];
    }
}
int query(int x)
{
    int res = 0;
    while (top[x])
    {
        res = (res + query1(1, dfn[top[x]], dfn[x])) % mod;
        x = fa[top[x]];
    }
    return res;
}
int ans[MAXN];
signed main()
{
    n = read(), m = read(), t = read();
    for (int i = 1; i <= n; i++)
        mi[i] = quickpow(i, t);
    for (int i = 2; i <= n; i++)
    {
        int x = read();
        add(x, i), add(i, x);
    }
    dfs1(1, 0), dfs2(1, 0);
    build(1, 1, n);
    for (int i = 1; i <= m; i++)
    {
        int x = read(), y = read();
        q[i] = (question){x, y, i};
    }
    sort(q + 1, q + m + 1);
    int now = 1;
    for (int i = 1; i <= n; i++)
    {
        modefy(i);
        while (q[now].u <= i && now <= m)
        {
            ans[q[now].id] = (ans[q[now].id] + query(q[now].z)) % mod;
            now++;
        }
    }
    for (int i = 1; i <= m; i++)
        printf("%lld\n", ans[i]);
    return 0;
}