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

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

思路：

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

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

 1 // #pragma comment(linker, "/STACK:102c000000,102c000000")
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <sstream>
 6 #include <string>
 7 #include <algorithm>
 8 #include <list>
 9 #include <map>
10 #include <vector>
11 #include <queue>
12 #include <stack>
13 #include <cmath>
14 #include <cstdlib>
15 // #include <conio.h>
16 using namespace std;
17 #define pi acos(-1.0)
18 const int N = 1e5+10;
19 const int MOD = 1e9+7;
20 #define inf 0x7fffffff
21 typedef long long  LL;
22 
23 void frein(){freopen("in.txt","r",stdin);}
24 void freout(){freopen("out.txt","w",stdout);}
25 inline LL read(){LL x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9') { x=x*10+ch-'0';ch=getchar();}return x*f;}
26 const int M =35;
27 
28 int f[N][M];
29 LL sum[N][M];
30 int mn[N][M];
31 int main(){
32     int n;
33     LL k;
34     n=read(),k=read();
35     for(int i=0;i<n;i++) scanf("%d",&f[i][0]);
36     for(int i=0;i<n;i++) {scanf("%d",&sum[i][0]);mn[i][0]=sum[i][0];}
37     for(int j=1;j<M;j++){
38         for(int i=0;i<n;i++){
39             f[i][j]=f[f[i][j-1]][j-1];
40             sum[i][j]=sum[f[i][j-1]][j-1]+sum[i][j-1];
41             mn[i][j]=min(mn[i][j-1],mn[f[i][j-1]][j-1]);
42         }
43     }
44     LL ans;
45     for(int i=0;i<n;i++){
46         int v=i,minn=inf;
47         LL K=k;
48         ans=0;
49         for(int j=M-1;j>=0;j--){
50             if((1LL<<j)<=K){
51                 ans+=sum[v][j];
52                 minn=min(minn,mn[v][j]);
53                 v=f[v][j];
54                 K-=(1LL<<j);
55             }
56         }
57         printf("%I64d %d
",ans,minn);
58     }
59     return 0;
60 }