C++ 解法, 执行用时: 160ms, 内存消耗: 16704K, 提交时间: 2022-04-03 23:57:16

#include<bits/stdc++.h>
#define File(name) freopen(#name".in", "r", stdin); freopen(#name".out", "w", stdout);
#define int long long
using namespace std;
using ll = long long;
using ull = unsigned long long;
template<typename T>
inline T read(){
    T n = 0; int f = 1; char ch = getchar();
    while(!isdigit(ch)){
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(isdigit(ch)){
        n = n * 10 + ch - '0';
        ch = getchar();
    }
    return f * n;
}
template<typename T>
void write(T n){
    if(n/10) write(n/10);
    putchar(n%10+'0');
}
void input() {}
template<typename Type, typename... Types>
void input(Type &arg, Types&... args){
    arg = read<Type>();
    input(args...);
}
namespace Main{
    const int N = 50005;
    const int MOD = 998244353;
    int n, m, k, a[N], siz[N], fa[N], son[N], dep[N], top[N], dfn[N], dfnCnt;
    vector<int> g[N];
    int ans[N];
    vector<pair<int, int>> q[N];
    struct segtree{
        struct segtree_node{
            int l, r, sum, wei, add;
        }t[N<<2];
        #define ls p<<1
        #define rs p<<1|1
        void pushup(int p){
            t[p].wei = (t[ls].wei + t[rs].wei) % MOD;
            t[p].sum = (t[ls].sum + t[rs].sum) % MOD;
        }
        void pushadd(int p, int k){
            t[p].sum = (t[p].sum + t[p].wei * k % MOD) % MOD;
            t[p].add = (t[p].add + k) % MOD;
        }
        void pushdown(int p){
            if(t[p].add){
                pushadd(ls, t[p].add);
                pushadd(rs, t[p].add);
                t[p].add = 0;
            }
        }
        void build(int p, int l, int r){
            t[p].l = l, t[p].r = r;
            if(t[p].l == t[p].r){
                t[p].wei = a[l];
                return;
            }
            int mid = l + r >> 1;
            build(ls, l, mid);
            build(rs, mid + 1, r);
            pushup(p);
        }
        void modify(int p, int l, int r){
            if(t[p].l >= l && t[p].r <= r){
                pushadd(p, 1);
                return;
            }
            int mid = t[p].l + t[p].r >> 1;
            pushdown(p);
            if(mid >= l) modify(ls, l, r);
            if(mid < r) modify(rs, l, r);
            pushup(p);
        }
        int query(int p, int l, int r){
            if(t[p].l >= l && t[p].r <= r) return t[p].sum;
            int mid = t[p].l + t[p].r >> 1, res = 0;
            pushdown(p);
            if(mid >= l) res = (res + query(ls, l, r)) % MOD;
            if(mid < r) res = (res + query(rs, l, r)) % MOD;
            return res;
        }
        #undef ls
        #undef rs
    }tree;
    void dfs1(int u){
        dep[u] = dep[fa[u]] + 1;
        siz[u] = 1;
        son[u] = -1;
        for(int v: g[u]){
            dfs1(v);
            siz[u] += siz[v];
            if(son[u] == -1 || siz[v] > siz[son[u]]) son[u] = v;
        }
    }
    void dfs2(int u, int t){
        top[u] = t;
        dfn[u] = ++dfnCnt;
        if(son[u] == -1) return;
        dfs2(son[u], t);
        for(int v: g[u]) if(v != son[u]) dfs2(v, v);
    }
    void addPath(int u, int v){
        while(top[u] != top[v]){
            if(dep[top[u]] < dep[top[v]]) swap(u, v);
            tree.modify(1, dfn[top[u]], dfn[u]);
            u = fa[top[u]];
        }
        if(dfn[u] > dfn[v]) swap(u, v);
        tree.modify(1, dfn[u], dfn[v]);
    }
    int queryPath(int u, int v){
        int res = 0;
        while(top[u] != top[v]){
            if(dep[top[u]] < dep[top[v]]) swap(u, v);
            res = (res + tree.query(1, dfn[top[u]], dfn[u])) % MOD;
            u = fa[top[u]];
        }
        if(dfn[u] > dfn[v]) swap(u, v);
        res = (res + tree.query(1, dfn[u], dfn[v])) % MOD;
        return res;
    }
    int qpow(int n, int k){
        int res = 1;
        while(k > 0){
            if(k & 1) res = res * n % MOD;
            n = n * n % MOD;
            k >>= 1;
        }
        return res;
    }
    void Main(){
        input(n, m, k);
        for(int i = 2, f; i <= n; i++){
            input(f);
            g[f].push_back(i);
            fa[i] = f;
        }
        dfs1(1);
        dfs2(1, 1);
        for(int i = 1; i <= n; i++) a[dfn[i]] = (qpow(dep[i], k) - qpow(dep[i] - 1, k) + MOD) % MOD;
        tree.build(1, 1, dfnCnt);
        for(int i = 0, p, z; i < m; i++){
            input(p, z);
            q[p].emplace_back(z, i);
        }
        for(int i = 1; i <= n; i++){
            addPath(i, 1);
            for(pair<int, int> x: q[i]) ans[x.second] = queryPath(x.first, 1);
        }
        for(int i = 0; i < m; i++) write(ans[i]), puts("");
        return;
    }
} // namespace
signed main(){
#ifdef Liuxizai
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif // Liuxizai
    Main::Main();
    return 0;
}