#P18169. Crawling on a Tree

Crawling on a Tree

Crawling on a Tree

有一棵包含 nn 个顶点的树,顶点编号为 1,2,…,n1,2,\ldots,n。最初有 mm 只乌龟位于顶点 1,它们可以沿树边向任意方向移动。

第 ii 条边的长度为 lil_i,最多能承受乌龟经过 kik_i 次。在第 kik_i 次经过后,这条边会断裂,之后不能再经过。双向经过都计数;同一只乌龟来回经过也分别计数。若多只乌龟同时经过同一条边,必须按乌龟只数计入经过次数,不能超过剩余容量。

你需要指挥乌龟移动,使每个顶点 ii(2≤i≤n2\le i\le n)至少被 cic_i 只不同的乌龟访问。同一只乌龟多次访问一个顶点,只能对该顶点计数一次。

求满足要求时,所有乌龟移动距离之和的最小值;如果无法满足要求,回答无解。乌龟不必返回顶点 1,可以在任意顶点停止,也可以一直留在起点。

你需要分别求出 m=1,2,…,Mm=1,2,\ldots,M 时的答案。

输入格式

第一行两个整数 n,Mn,M(2≤n≤1042\le n\le10^4,1≤M≤1041\le M\le10^4)。

接下来 n−1n-1 行,每行四个整数 ui,vi,li,kiu_i,v_i,l_i,k_i,表示一条连接顶点 uiu_i 与 viv_i 的无向边,长度为 lil_i,最多允许 kik_i 次经过。

其中 1≤ui,vi≤n1\le u_i,v_i\le n,ui≠viu_i\ne v_i,1≤li,ki≤1091\le l_i,k_i\le10^9。保证这些边构成一棵树。

最后一行 n−1n-1 个整数 c2,c3,…,cnc_2,c_3,\ldots,c_n(1≤ci≤M1\le c_i\le M)。

输出格式

输出 MM 行。第 ii 行输出 m=im=i 时的最小总移动距离;若无解,输出 -1。

样例 1

输入:

4 2
1 2 3 2
2 3 2 1
2 4 5 1
1 1 1

输出:

-1
13

只有一只乌龟时,它不能同时访问顶点 3 和 4:到达其中一个叶子后,所经过的容量为 1 的边立即断裂。

有两只乌龟时,可以让它们都从 1 到 2,然后一只到 3,另一只到 4。总距离为 (3+2)+(3+5)=13(3+2)+(3+5)=13。

样例 2

输入:

4 2
1 2 3 2
2 3 2 1
2 4 5 1
2 2 2

输出:

-1
-1