一道非常好的练倍增的题目

思路很简单,就是倍增处理出每个点往后$2^i$个点的路径权值和与最小值,同时要注意一下$k​$要用longlong存,否则会挂掉

如果不会倍增的右转百度找其他博客去吧……我这里就不赘述了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>

using namespace std;

int Son[100010][50];
long long Ans[100010][50];
int Min[100010][50];

long long Solve1(int Cur, long long k){ // 求出Cur向后k条路径的权值和
if(k == 0)
return 0;
int xx = 0;
long long x = 1; // 由于2 ^ xx 会爆int,所以应当开一个变量专门存
while(x <= k)
xx++, x <<= 1;
xx--;
x >>= 1;
return Ans[Cur][xx] + Solve1(Son[Cur][xx], k - x);
}

int Solve2(int Cur, long long k){ // 求出Cur向后k条路径的权值最小值
if(k == 0)
return 2147483647;
int xx = 0;
long long x = 1; // 与上面同理
while(x <= k)
xx++, x <<= 1;
xx--;
x >>= 1;
return min(Min[Cur][xx], Solve2(Son[Cur][xx], k - x));
}

int main(){
int n;
long long k;
scanf("%d %I64d", &n, &k);
for(int i = 0; i < n; i++)
scanf("%d", &Son[i][0]);
for(int i = 0; i < n; i++)
scanf("%I64d", &Ans[i][0]), Min[i][0] = Ans[i][0];
for(int t = 1; t <= 40; t++) // 预处理出第2^i辈儿子
for(int i = 0; i < n; i++)
Son[i][t] = Son[Son[i][t-1]][t-1];
for(int t = 1; t <= 40; t++) // 预处理往后$2^i$个点的路径权值之和
for(int i = 0; i < n; i++)
Ans[i][t] = Ans[i][t-1] + Ans[Son[i][t-1]][t-1];
for(int t = 1; t <= 40; t++) // 预处理往后$2^i$个点的路径权值最小值
for(int i = 0; i < n; i++)
Min[i][t] = min(Min[i][t-1], Min[Son[i][t-1]][t-1]);
for(int i = 0; i < n; i++)
printf("%I64d %d\n", Solve1(i, k), Solve2(i, k));
}

 评论