P6419 [COCI 2014/2015 #1] Kamp

一颗树 $n$ 个点，$n-1$ 条边，经过每条边都要花费一定的时间，任意两个点都是联通的。 有 $K$ 个人（分布在 $K$ 个不同的点）要集中到一个点举行聚会。 聚会结束后需要一辆车从举行聚会的这点出发，把这 $K$ 个人分别送回去。 请你回答，对于 $i=1 \sim n$ ，如果在第 $i$ 个点举行聚会，司机最少需要多少时间把 $K$ 个人都送回家。

无

无

#### 数据规模与约定 - 对于 $50\%$ 的数据，保证 $n\le 2\times 10^3$。 - 对于 $100\%$ 的数据， $1 \le k \le n \leq 5\times 10^5$，$1 \le x,y \le n$，$1 \le z \le 10^8$ 。