codeforce 702E Analysis of Pathes in Functional Graph RMQ+二进制

http://codeforces.com/contest/702

题意：n个点，n条边，每个点出边只有一条，问从每个点出发经过k条边的边权和，以及边权最小值

思路：

f[i][j] 第i个点出发，经过2^j条边后的相连点 其余类似

二进制巧妙解决问题应用太广了

 // #pragma comment(linker, "/STACK:102c000000,102c000000")

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <sstream>

 #include <string>

 #include <algorithm>

 #include <list>

 #include <map>

 #include <vector>

 #include <queue>

 #include <stack>

 #include <cmath>

 #include <cstdlib>

 // #include <conio.h>

 using namespace std;

 #define pi acos(-1.0)

 const int N = 1e5+;

 const int MOD = 1e9+;

 #define inf 0x7fffffff

 typedef long long  LL;

 void frein(){freopen("in.txt","r",stdin);}

 void freout(){freopen("out.txt","w",stdout);}

 inline LL read(){LL x=,f=;char ch=getchar();while(ch>''||ch<'') {if(ch=='-') f=-;ch=getchar();}while(ch>=''&&ch<='') { x=x*+ch-'';ch=getchar();}return x*f;}

 const int M =;

 int f[N][M];

 LL sum[N][M];

 int mn[N][M];

 int main(){

     int n;

     LL k;

     n=read(),k=read();

     for(int i=;i<n;i++) scanf("%d",&f[i][]);

     for(int i=;i<n;i++) {scanf("%d",&sum[i][]);mn[i][]=sum[i][];}

     for(int j=;j<M;j++){

         for(int i=;i<n;i++){

             f[i][j]=f[f[i][j-]][j-];

             sum[i][j]=sum[f[i][j-]][j-]+sum[i][j-];

             mn[i][j]=min(mn[i][j-],mn[f[i][j-]][j-]);

         }

     }

     LL ans;

     for(int i=;i<n;i++){

         int v=i,minn=inf;

         LL K=k;

         ans=;

         for(int j=M-;j>=;j--){

             if((1LL<<j)<=K){

                 ans+=sum[v][j];

                 minn=min(minn,mn[v][j]);

                 v=f[v][j];

                 K-=(1LL<<j);

             }

         }

         printf("%I64d %d\n",ans,minn);

     }

     return ;

 }