暑期cspj模拟赛9

T4

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 50;
const int LOG = 40;

int nxt[N];           // 每个节点的下一个节点
long long sum[N][LOG+5]; // sum[i][j]: 从i出发走2^j步的节点编号和
int to[N][LOG+5];     // to[i][j]: 从i出发走2^j步到达的节点

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    // 读取图结构
    for (int i = 1; i <= n; ++i) {
        cin >> nxt[i];
    }

    // 预处理倍增表
    for (int i = 1; i <= n; ++i) {
        to[i][0] = nxt[i];
        sum[i][0] = nxt[i];
    }

    for (int j = 1; j <= LOG; ++j) {
        for (int i = 1; i <= n; ++i) {
            to[i][j] = to[to[i][j-1]][j-1];
            sum[i][j] = sum[i][j-1] + sum[to[i][j-1]][j-1];
        }
    }

    // 处理查询
    while (q--) {
        int x;
        long long k;
        cin >> x >> k;

        long long ans = 0;
        int cur = x;
        
        // 使用倍增法计算路径和
        for (int j = LOG; j >= 0; --j) {
            if (k >= (1LL << j)) {
                ans += sum[cur][j];
                cur = to[cur][j];
                k -= (1LL << j);
            }
        }

        cout << ans << '\n';
    }

    return 0;
}