1114: [视频]树形动态规划（TreeDP）3.0：多叉苹果树【scy改编ural1018二叉苹果树】
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 2 Solved: 2
[Status] [Submit] [Creator:]
Description
有一棵苹果树，如果树枝有分叉，可以是分多叉，分叉数k>=0（就是说儿子的结点数大于等于0）这棵树共有N个结点（叶子点或者树枝分叉点），编号为1~~N,树根编号一定是1。我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有4个树枝的树
现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。给定需要保留的树枝数量，求出最多能留住多少苹果。
输入格式:
输入第一行包含两个整数n，k(1<=k 输入接下来的n – 1行，每一行包含三个整数x，y，c，表示节点x和y之间有一条树枝。c表示这根树枝上苹果的数量。
输出格式：
输出一行，为最多可以保留的苹果数。
Input
6 2
1 3 1
1 4 10
1 6 21
2 3 20
3 5 20
Output
31
数据规模：
对于20%的数据，满足1 <= n <=15。
对于40%的数据，满足1 <= n <=100。
对于100%的数据，满足1 <= n <=310。
现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。给定需要保留的树枝数量，求出最多能留住多少苹果。
输入格式:
输入第一行包含两个整数n，k(1<=k 输入接下来的n – 1行，每一行包含三个整数x，y，c，表示节点x和y之间有一条树枝。c表示这根树枝上苹果的数量。
输出格式：
输出一行，为最多可以保留的苹果数。
Input
6 2
1 3 1
1 4 10
1 6 21
2 3 20
3 5 20
Output
31
数据规模：
对于20%的数据，满足1 <= n <=15。
对于40%的数据，满足1 <= n <=100。
对于100%的数据，满足1 <= n <=310。
HINT
