#P8273. [2017年yali集训]河取的机器人

    ID: 8356 传统题 1000ms 256MiB 尝试: 3 已通过: 2 难度: 7 上传者: 标签>动态规划图论CF2200树形DP背包DPDFS搜索BFS

[2017年yali集训]河取的机器人

河取的机器人(Kawashiro)

(kawashiro.cpp/c/pas)

题目描述

河城河取正在研究她的 power 收集机器人,现在到了实地检测的时候了河取的实验场地选在妖怪之山的山麓.妖怪山的山麓由 n 个路口和 n-1 条小路组成,且从任意路口出发都能通过小路到达其它任意路口.

河取会把她的 k 个机器人放在某一个路口.机器人可以沿着小路走,每一条小路只要有一个机器人走过,就可以收集小路上的所有 power.每个机器人都可以停在任意一个地方.不过,现阶段机器人移动耗能非常大,所以河城河取想知道,收集完所有的 power,机器人经过的最小距离和.

输入格式

从标准输入读入。第一行为两个整数 n,k

接下来 n-1 行,每行三个整数 s,t,v,分别代表一条小路的起点,终点和长度

输出格式

向标准输出写出。

一共 n 行 n 个整数,第 i 行的整数表示如果所有的机器人都从 i 号点出发, 经过的最小距离和

当 n=1n=1 时,没有道路需要收集,输出 0。当 n>1n>1 且 k=0k=0 时,无法收集全部道路,全部 nn 行均输出 -1。

样例输入1

5 3
1 2 8
2 3 3
3 4 14
3 5 7

样例输出1

39
35
32
39
39

数据规模与约定

对于 10%的数据,满足 n<=10,k<=2 对于 30%的数据,满足 n<=100,k<=12 对于 50%的数据,满足 n<=1000,k<=20 对于另外 10%的数据,满足 k<=2 对于 100%的数据,满足 1<=n<=100000,0<=k<=30,1<=v<=1000