#2852. 作业大会

作业大会

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

可爱的凯文在高一时就统计了所有人的联系方式,完成了教一的通讯录。每年的寒暑 假开作业大会的时候这张通讯录就充分发挥了作用。同志们根据这张通讯录制定了通讯网络, 可以抽象成一棵树。

每个节点(除叶子节点)首先接受他的所有孩子节点完成的卷子.接着他选择可以完 成任意一张未完成的卷子,也可以选择不做。

最后所有完成的卷子被汇总到树根节点。 很显然做卷子是要消耗时间的,卷子从孩子传到父亲也是要耗时间的。你的任务就是 安排一个计划使得消耗最少时间完成所有卷子并汇总到树根。

输入格式

第一行两个整数 n\red{n,}m\red{m}。表示人数和卷子总数。

接下来 n1\red{n-1 }行每行三个整数 x\red{x,}y\red{y,}c\red{c}。表示 x\red{x }y\red{y }连通,在 x\red{x }y\red{y }之间传递时间为 c\red{c}

最后 n\red{n }行,每行 m\red{m }个整数。第 i\red{i }行第 j\red{j }列的整数是编号 i\red{i }的节点完成第 j\red{j }张卷子消耗 的时间。

n<=55\red{n<=55,}m<=11\red{m<=11,}保证 n>=m\red{n>=m}。根节点的编号为 1\red{1}

输出格式

一个整数 t\red{t}。表示消耗的最小总时间。保证答案在 longint\red{longint }范围内。

样例

输入样例

6 3
1 2 1
1 3 1
2 4 1
2 5 1
3 6 1
3 4 3
3 2 5
6 1 2
1 8 9
8 8 1
4 7 6

输出样例

7

提示

数据说明:

50%\red{50\%}的数据有 n<=10\red{n<=10,}m<=5\red{m<=5}

国庆集训10

未参加
状态
已结束
规则
IOI
题目
3
开始于
2022-10-5 9:00
结束于
2022-10-5 12:00
持续时间
3 小时
主持人
参赛人数
12