#Pmp19. 3.图上查询

3.图上查询

3.图上查询

题目描述

$有一个n个点n条边的有向图,第i条边从i-1指向f_i,边权为w_i的边,对每个点求从它出发经过k条边,这k条边的权值和s_i以及这k条边$的权值最小值mi最小值m_i。

输入格式

第一行两个数n和k。

第二行n个数fif_i。

第三行n个数wiw_i。

输出格式

每行两个数si和mis_i和m_i。

数据范围

(原站未提供,导入后需人工补齐)

样例

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

提示

对于30%的数据:n,k<=103n,k<=10^3。

对于100%的数据:1<=n<=105,1<=k<=1010,0<=fi<=n,1<=wi<=1081<=n<=10^5,1<=k<=10^10,0<=f_i<=n,1<=w_i<=10^8。