303635: CF702E. Analysis of Pathes in Functional Graph

Memory Limit:512 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Analysis of Pathes in Functional Graph

题意翻译

题目描述】 有一个n个点n条边的带权有向图(点编号0~n-1),每个点有且仅有一条出边,对于每个点i求出由i出发经过k条边,这k条边的权值最小值和权值和。 【输入格式】 第一行两个正整数n和k。 第二行n个正整数,第i个数表示i的出边指向的点。 第三行n个正整数,第i个数表示i的出边的权值。 【输出格式】 共n行,每行两个数,第一个数表示由点i出发经过k条边,这k条边的权值和,第二个数则表示权值的最小值。

题目描述

You are given a functional graph. It is a directed graph, in which from each vertex goes exactly one arc. The vertices are numerated from 0 to $ n-1 $ . Graph is given as the array $ f_{0},f_{1},...,f_{n-1} $ , where $ f_{i} $ — the number of vertex to which goes the only arc from the vertex $ i $ . Besides you are given array with weights of the arcs $ w_{0},w_{1},...,w_{n-1} $ , where $ w_{i} $ — the arc weight from $ i $ to $ f_{i} $ . ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF702E/3cc14f84d85a536673d301b325eadbda33e38d15.png)The graph from the first sample test.Also you are given the integer $ k $ (the length of the path) and you need to find for each vertex two numbers $ s_{i} $ and $ m_{i} $ , where: - $ s_{i} $ — the sum of the weights of all arcs of the path with length equals to $ k $ which starts from the vertex $ i $ ; - $ m_{i} $ — the minimal weight from all arcs on the path with length $ k $ which starts from the vertex $ i $ . The length of the path is the number of arcs on this path.

输入输出格式

输入格式


The first line contains two integers $ n,k $ ( $ 1<=n<=10^{5},1<=k<=10^{10} $ ). The second line contains the sequence $ f_{0},f_{1},...,f_{n-1} $ ( $ 0<=f_{i}&lt;n $ ) and the third — the sequence $ w_{0},w_{1},...,w_{n-1} $ ( $ 0<=w_{i}<=10^{8} $ ).

输出格式


Print $ n $ lines, the pair of integers $ s_{i} $ , $ m_{i} $ in each line.

输入输出样例

输入样例 #1

7 3
1 2 3 4 3 2 6
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
0 1 2 3
0 1 2 3

输出样例 #2

0 0
4 1
8 2
12 3

输入样例 #3

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

输出样例 #3

7 1
17 1
19 2
21 3
8 1

Input

题意翻译

题目描述】 有一个n个点n条边的带权有向图(点编号0~n-1),每个点有且仅有一条出边,对于每个点i求出由i出发经过k条边,这k条边的权值最小值和权值和。 【输入格式】 第一行两个正整数n和k。 第二行n个正整数,第i个数表示i的出边指向的点。 第三行n个正整数,第i个数表示i的出边的权值。 【输出格式】 共n行,每行两个数,第一个数表示由点i出发经过k条边,这k条边的权值和,第二个数则表示权值的最小值。

加入题单

上一题 下一题 算法标签: