原题链接

点我跳转原题

题目描述

有一个 $n$ 个点 $n$ 条边的带权有向图（点编号 $0\sim n-1$），每个点有且仅有一条出边。

• 记 $f_i$ 为点 $i$ 出边连向的顶点编号。由输入给出
• 记 $w_i$ 为 $i\to f_i$ 的边权。

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

输入格式

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

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

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

输出格式

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

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

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

4 4
0 1 2 3
0 1 2 3

0 0
4 1
8 2
12 3

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

7 1
17 1
19 2
21 3
8 1

提示

数据范围

• $1\leq n\leq 10^5$
• $1\leq k\leq 10^{10}$
• $0\leq w_i\leq 10^8$。
• $0\leq f_i<n$