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; }
