记录编号	582313	评测结果	AAAAAAAAAA
题目名称	Analysis of Pathes in Functional Graph	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	2.629 s
提交时间	2023-09-09 14:39:44	内存使用	68.45 MiB

#include <bits/stdc++.h>
#define pb emplace_back
#define fir first
#define sec second

using i64 = long long;
using pii = std::pair<int, int>;

const int maxn = 1e5 + 5;
int anc[40][maxn], mnv[40][maxn], n, ord[maxn], v[maxn];
i64 sum[40][maxn], w, s[maxn];

int main() {
	freopen("pathsjump.in", "r", stdin);
	freopen("pathsjump.out", "w", stdout);
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr); std::cout.tie(nullptr);
	std::cin >> n >> w;
	for(int i = 1;i <= n;++ i) {
		std::cin >> anc[0][i];
	}
	for(int i = 1;i <= n;++ i) {
		std::cin >> mnv[0][i];
		sum[0][i] = mnv[0][i];
	}
	for(int k = 1;k < 40;++ k) {
		for(int i = 1;i <= n;++ i) {
			anc[k][i] = anc[k - 1][anc[k - 1][i]];
			mnv[k][i] = std::min(mnv[k - 1][i], mnv[k - 1][anc[k - 1][i]]);
			sum[k][i] = sum[k - 1][i] + sum[k - 1][anc[k - 1][i]];
		}
	}
	for(int i = 1;i <= n;++ i) {
		ord[i] = i;
		s[i] = 0;
		v[i] = 1e9;
	}
	for(int k = 39;~ k;-- k) {
		if(w >> k & 1) {
			for(int i = 1;i <= n;++ i) {
				s[i] += sum[k][ord[i]];
				v[i] = std::min(v[i], mnv[k][ord[i]]);
				ord[i] = anc[k][ord[i]];
			}
		}
	}
	for(int i = 1;i <= n;++ i) {
		std::cout << s[i] << ' ' << v[i] << std::endl;
	}
	return 0;
}