ABC round 438 E st倍增

Problem Statement

There are N people and N buckets. Both the people and buckets are numbered 1,2,…,N.

Initially, person i holds only bucket i, and bucket i is empty.

From now on, the following operation will be performed 109 times:

• For i=1,2,…,Nsimultaneously, person i adds i units of water to each of the buckets they are holding and passes those buckets to person Ai​.

Here, there is no limit on the amount of water that can be put in a bucket.

For i=1,2,…,Q, answer the following queries:

• Find the amount of water in bucket Bi​ immediately after the Ti​-th operation.

问题陈述

• 有 N 人和 N 桶。人和水桶的编号都是 1,2,…,N 。

  最初，人 i 只持有水桶 i ，而水桶 i 是空的。

  从现在起，将执行以下操作 109 次：

• 对于 i=1,2,…,N同时*， i 将 i 个单位的水添加到他们手中的每个水桶中，并将这些水桶递给 Ai​ 。

• 在这里，水桶中的水量没有限制。

  对于 i=1,2,…,Q ，请回答下列问题：

• 求 Ti​ /-操作后，水桶 Bi​ 中的水量。

Input

The input is given from Standard Input in the following format:

N Q A1​ A2​ … AN​ T1​ B1​ T2​ B2​ ⋮ TQ​ BQ​

Output

Output Q lines. The i-th line should contain the answer to the i-th query.

我们设st[i][j]表示i 拿到水桶后 经过1<<j时间 水桶传递给谁 sum[i][j] 表示从i拿到某个水桶后 1<<j这个时间后 水桶的增加量 然后进行查询即可

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e5+5; ll sum[N][30],st[N][30]; int n,q; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>q; for(int i=1;i<=n;i++){ cin>>st[i][0]; sum[i][0]=i; } for(int i=1;i<30;i++){ for(int j=1;j<=n;j++){ st[j][i]=st[st[j][i-1]][i-1]; sum[j][i]=sum[st[j][i-1]][i-1]+sum[j][i-1]; } } while(q--){ ll res=0; ll t,b; cin>>t>>b; for(int i=0;i<30;i++){ if(t&(1LL<<i)){ res+=sum[b][i]; b=st[b][i]; } } cout<<res<<'\n'; } return 0; }