#P18926. [2026多校联测]公交

[2026多校联测]公交

公交

题目描述

有 nn 座城市,彼此间通过 n−1n-1 条道路连接且 nn 座城市互相连通。第 ii 座城市有 aia_i 个人。假设首都是 rr,现在你要修建 kk 条到 rr 的公交线路。若你选择修建线路 (u,r)(u,r),则 uu 到 rr 上的所有点都将被包括在公交线路中。对于不在公交线路上的点,居民需要沿最短路径走到一条最近的被包括在公交线路的点上,所产生的不满度为此距离乘上该点的人数。

你需要合理规划这 kk 条线路,使得不满度之和最小。同时,你需要求出首都为 1∼n1\sim n 的所有情况的答案。

输入格式

第一行两个整数 n,kn,k。

第二行 nn 个整数表示 aia_i。

接下来的 n−1n-1 行每行两个整数 u,vu,v,表示一条边。

输出格式

一行 nn 个整数,表示首都为 1…n1\dots n 时的答案。

样例输入

5 2
82822 92268 1983 93812 57626
1 2
2 3
2 4
4 5

样例输出

0 1983 0 1983 0

数据范围与约定

对于所有数据,1≤k≤n≤2×1051\le k\le n\le 2\times 10^5,0≤ai≤1050\le a_i\le 10^5。

数据点 n≤n\le k≤k\le
11 100100 nn
2,32,3 10310^3
44 10510^5 11
5,65,6 1010
7,87,8 nn
9,109,10 2×1052\times 10^5