CF702E Analysis of Pathes in Functional Graph(倍增)

发现每个点的出度为1，也就是说路径总是固定的，有观察到k很大，显然是通过倍增算法进行维护

 #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
typedef pair<int,pll> plll;
const int N=1e5+10;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
int n;
ll k;
ll mi[N][50];
ll f[N][50];
ll ans[N][50];
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>k;
    int i,j;
    for(i=0;i<n;i++){
        cin>>f[i][0];
    }
    for(i=0;i<n;i++){
        cin>>ans[i][0];
        mi[i][0]=ans[i][0];
    }
    for(ll i=1;i<50;++i){
        for(ll j=0;j<n;++j){
            ll nxt=f[j][i-1];
            f[j][i]=f[nxt][i-1];
            ans[j][i]=ans[j][i-1]+ans[nxt][i-1];
            mi[j][i]=min(mi[j][i-1],mi[nxt][i-1]);
        }
    }
    for(ll u=0;u<n;++u){
        ll s=0,mx=1e18,pos=u,x=k;
        for(ll i=49;i>=0;--i)
            if((x>>i)&1) s+=ans[pos][i],mx=min(mx,mi[pos][i]),pos=f[pos][i];
        cout<<s<<" "<<mx<<endl;
    }
    return 0;
}