---

题目大意

给定一棵 $n$ 个节点的有根树，根为 $1$，每个询问 $(x, y)$ 要求计算：

$$\sum_{i=1}^x \text{depth}(\text{lca}(i,y))^k$$

其中 $\text{depth}(u)$ 表示节点 $u$ 的深度（根深度为 $1$），$k$ 是给定的常数，答案对 $998244353$ 取模。

---

样例分析

样例树结构：

1 (深度1)
├── 4 (深度2)  
│   └── 5 (深度3)
└── 2 (深度2)
    └── 3 (深度3)

第一个询问 $(x=4, y=3)$：

• $\text{lca}(1,3)=1$, 深度 $1$, $1^2=1$
• $\text{lca}(2,3)=1$, 深度 $1$, $1^2=1$
• $\text{lca}(3,3)=3$, 深度 $3$, $3^2=9$
• $\text{lca}(4,3)=4$, 深度 $2$, $2^2=4$

总和 = $1 + 1 + 9 + 4 = 15$

---

暴力做法（不可行）

直接对每个询问枚举 $i=1 \dots x$，计算 $\text{lca}(i,y)$ 并求深度的 $k$ 次方。

复杂度：$O(Q \cdot n \cdot \text{LCA时间})$，对于 $n,Q \le 50000$ 不可行。

---

关键观察

我们需要利用树上前缀和的思想。

重要性质：对于固定的 $y$，考虑从根到 $y$ 的路径上的节点，对于任意 $i$，$\text{lca}(i,y)$ 一定是这个路径上的某个节点。

更具体地：

• 从根到 $y$ 的路径记为 $p_1, p_2, \dots, p_m$（$p_1=1$, $p_m=y$）
• 对于任意 $i$，$\text{lca}(i,y)$ 是路径上深度最大的、同时是 $i$ 的祖先的节点

---

转化为路径标记问题

我们可以这样理解：

• 把从根到 $y$ 的路径上的每个节点 $u$ 标记一个"价值" $\text{depth}(u)^k$
• 对于节点 $i$，它对答案的贡献是它到根的路径与 $y$ 到根的路径交集中深度最大的节点的价值

换句话说：

• 每个节点 $u$ 对答案的贡献 = $\text{depth}(u)^k \times$（有多少个 $i \le x$ 满足 $\text{lca}(i,y) = u$）

---

离线处理与DFS序

标准解法是离线处理 + 树链剖分或DFS序：

算法框架

1. DFS预处理：求出每个节点的深度、DFS入序、出序、父节点等信息
2. 问题转化：对于询问 $(x,y)$，我们想求：$$\sum_{u \in \text{path}(1,y)} \text{depth}(u)^k \times [\text{以 u 为 lca 且编号 ≤ x 的 i 的个数}] $$
3. 关键技巧：以 $u$ 为 lca 意味着 $i$ 在 $u$ 的子树中，且 $y$ 也在 $u$ 的子树中（实际上 $u$ 是 $i$ 和 $y$ 的公共祖先）

---

高效解法：树上差分 + 数据结构

更优雅的解法是利用树上差分思想：

定义 $f(u) = \text{depth}(u)^k$。

对于询问 $(x,y)$，答案可以表示为：

$$\text{ans} = \sum_{u \in \text{path}(1,y)} f(u) \times \text{cnt}_u $$

其中 $\text{cnt}_u$ 表示满足 $i \le x$ 且 $u$ 是 $i$ 的祖先的 $i$ 的个数。

---

具体实现步骤

方法一：树链剖分 + 离线处理

1. DFS预处理：求出父节点、深度、子树大小、重儿子、DFS序等
2. 树链剖分：将树分解为若干重链
3. 离线处理询问：按 $x$ 排序
4. 逐步插入节点：用数据结构维护当前所有 $i \le x$ 的节点信息
5. 查询路径和：对于每个 $y$，查询从根到 $y$ 路径上所有节点的贡献和

方法二：DFS序 + Fenwick树/线段树

更简单的实现：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 998244353;
const int N = 50005;

vector<int> g[N];
int dep[N], fa[N], in[N], out[N], idx;
ll depth_power[N];  // depth_power[u] = dep[u]^k mod MOD
int n, Q, k;

// 快速幂
ll qpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

void dfs(int u, int p) {
    fa[u] = p;
    dep[u] = dep[p] + 1;
    in[u] = ++idx;
    depth_power[u] = qpow(dep[u], k);
    
    for (int v : g[u]) {
        if (v == p) continue;
        dfs(v, u);
    }
    out[u] = idx;
}

// Fenwick树
struct Fenwick {
    ll tr[N];
    void add(int x, ll v) {
        for (; x <= n; x += x & -x)
            tr[x] = (tr[x] + v) % MOD;
    }
    ll query(int x) {
        ll res = 0;
        for (; x; x -= x & -x)
            res = (res + tr[x]) % MOD;
        return res;
    }
} bit;

int main() {
    scanf("%d%d%d", &n, &Q, &k);
    for (int i = 2; i <= n; i++) {
        int f; scanf("%d", &f);
        g[f].push_back(i);
        g[i].push_back(f);
    }
    
    dep[0] = 0;
    idx = 0;
    dfs(1, 0);
    
    vector<tuple<int, int, int>> queries; // (x, y, id)
    for (int i = 0; i < Q; i++) {
        int x, y; scanf("%d%d", &x, &y);
        queries.emplace_back(x, y, i);
    }
    
    // 按x排序
    sort(queries.begin(), queries.end());
    
    vector<ll> ans(Q);
    int cur_x = 0;
    
    for (auto [x, y, id] : queries) {
        // 插入所有 cur_x+1 ... x 的节点
        while (cur_x < x) {
            cur_x++;
            // 将节点cur_x的贡献加到其所有祖先上
            int u = cur_x;
            while (u) {
                bit.add(in[u], depth_power[u]);
                u = fa[u];
            }
        }
        
        // 查询从根到y路径上的贡献和
        ll res = 0;
        int u = y;
        while (u) {
            res = (res + bit.query(in[u]) - bit.query(in[u] - 1) + MOD) % MOD;
            u = fa[u];
        }
        ans[id] = res;
    }
    
    for (ll res : ans) {
        printf("%lld\n", res);
    }
    return 0;
}

---

算法正确性

这个解法的核心思想是：

• 每个节点 $u$ 维护一个值：当前有多少个 $i \le x$ 以 $u$ 为祖先
• 当插入节点 $i$ 时，把它所有祖先的计数器加 $1$
• 对于询问 $(x,y)$，答案就是从根到 $y$ 路径上所有节点的（计数器值 × 深度幂次）之和

---

复杂度分析

• 预处理：$O(n)$
• 每个节点插入时更新所有祖先：最坏 $O(n)$，但树随机情况下接近 $O(\log n)$
• 每个查询需要遍历从 $y$ 到根的路径：$O(\text{深度})$
• 总复杂度：$O(n \cdot \text{平均深度} + Q \cdot \text{平均深度})$

对于链的情况最坏 $O(n^2)$，但实际数据通常不会卡满。

---

优化版本

对于大数据，需要使用树链剖分或全局平衡二叉树来将复杂度优化到 $O((n+Q)\log^2 n)$。

---

总结

本题的关键在于：

1. 将 LCA 深度和转化为路径上的节点贡献和
2. 利用离线处理按 $x$ 排序，逐步插入节点
3. 使用数据结构维护节点贡献，支持快速查询路径和

这种"逐步插入 + 路径查询"的思路是处理此类树上前缀和问题的经典方法。