#P18169. Crawling on a Tree
Crawling on a Tree
Crawling on a Tree
有一棵包含 个顶点的树,顶点编号为 。最初有 只乌龟位于顶点 1,它们可以沿树边向任意方向移动。
第 条边的长度为 ,最多能承受乌龟经过 次。在第 次经过后,这条边会断裂,之后不能再经过。双向经过都计数;同一只乌龟来回经过也分别计数。若多只乌龟同时经过同一条边,必须按乌龟只数计入经过次数,不能超过剩余容量。
你需要指挥乌龟移动,使每个顶点 ()至少被 只不同的乌龟访问。同一只乌龟多次访问一个顶点,只能对该顶点计数一次。
求满足要求时,所有乌龟移动距离之和的最小值;如果无法满足要求,回答无解。乌龟不必返回顶点 1,可以在任意顶点停止,也可以一直留在起点。
你需要分别求出 时的答案。
输入格式
第一行两个整数 (,)。
接下来 行,每行四个整数 ,表示一条连接顶点 与 的无向边,长度为 ,最多允许 次经过。
其中 ,,。保证这些边构成一棵树。
最后一行 个整数 ()。
输出格式
输出 行。第 行输出 时的最小总移动距离;若无解,输出 -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。总距离为 。
样例 2
输入:
4 2
1 2 3 2
2 3 2 1
2 4 5 1
2 2 2
输出:
-1
-1