P6670 [清华集训 2016] 汽水

牛牛来到了一个盛产汽水的国度旅行。 这个国度的地图上有 $n$ 个城市，这些城市之间用 $n−1$ 条道路连接，任意两个城市之间，都存在一条路径连接。这些城市生产的汽水有许多不同的风味，在经过道路 $i$ 时，牛牛会喝掉 $w_i$ 的汽水。牛牛非常喜欢喝汽水，但过量地饮用汽水是有害健康的，因此，他希望在他旅行的这段时间内，平均每天喝到的汽水的量尽可能地接近给定的一个正整数 $k$ 。 同时，牛牛希望他的旅行计划尽可能地有趣，牛牛会先选择一个城市作为起点，然后每天通过一条道路，前往一个没有去过的城市，最终选择在某一个城市结束旅行。 牛牛还要忙着去喝可乐，他希望你帮他设计出一个旅行计划，满足每天 $|P−k|$（$P$ 为平均每天喝到的汽水量）的值尽量小，请你告诉他这个最小值。

无

无

#### 样例解释 在图中，路径 $5\to1\to3$ 是一条最合适的路线，总计喝到的汽水的量是 $27+12=39$, 平均每天喝到的汽水量是 $39÷2=19.5$, $|19.5−21|=1.5$，向下取整后得到 $1$，因此答案是 $1$。 #### 数据范围 对于 $20\%$ 的数据，$n≤1000$。 对于另外 $20\%$ 的数据，保证编号为 $i(1≤i≤n−1)$ 的节点和编号为 $i+1$ 的节点之间连接了一条边。 对于另外 $20\%$ 的数据，保证数据是以 $1$ 为根的完全二叉树（在完全二叉树中，节点 $i(2≤i≤n)$ 和节点 $⌊i÷2⌋$ 之间有一条道路）。 对于另外 $20\%$ 的数据，保证除节点 $1$ 以外，其他节点和节点 $1$ 之间都有一条道路。 对于 $100\%$ 的数据，$1≤n≤5×10^4$，$0≤w_i≤10^{13}$，$0≤k≤10^{13}$。