3714. Analysis of Pathes in Functional Graph

【题目描述】

有一个 $n$ 个点 $n$ 条边的带权有向图，每个点有且仅有一条出边。

对于每个点 $i$ 求出由 $i$ 出发经过 $k$ 条边，这 $k$ 条边的权值最小值和权值和。

【输入格式】

第一行两个正整数 $n$ 和 $k$。

第二行 $n$ 个正整数，第 $i$ 个数表示 $i$ 的出边指向的点。

第三行 $n$ 个正整数，第 $i$ 个数表示 $i$ 的出边的权值 $w_i$。

【输出格式】

共 $n$ 行，每行两个数，第一个数表示由点 $i$ 出发经过 $k$ 条边，这 $k$ 条边的权值和，第二个数则表示权值的最小值。

【样例输入1】

7 3
2 3 4 5 4 3 7
6 3 1 4 2 2 3

【样例输出1】

10 1
8 1
7 1
10 2
8 2
7 1
9 3

【样例输入2】

4 4
1 2 3 4
0 1 2 3

【样例输出2】

0 0
4 1
8 2
12 3

【样例输入3】

5 3
2 3 4 5 1
4 1 2 14 3

【样例输出3】

7 1
17 1
19 2
21 3
8 1

【样例说明】

在此键入。

【数据规模与约定】

对于 30% 的数据，$1 \le k \le 100$。

对于 100% 的数据，$1 \le n \le 10^5, 1 \le k \le 10^{10},1 \le w_i \le 10^8$。

【来源】

lgc。