题目描述
有一棵苹果树，如果树枝有分叉，一定是分 2 叉（就是说没有只有 1 个儿子的结点）。 这棵树共有 N 个结点（叶子点或者树枝分叉点），编号为 1-N,树根编号一定是 1。 我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有 4 个树枝 的树： 2 5 \ / 3 4 \ / 1 现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。 给定需要保留的树枝数量，求出最多能留住多少苹果。
输入格式：
第 1 行 2 个数，N 和 Q(1<=Q<= N,1<N<=100)。 N 表示树的结点数，Q 表示要保留的树枝数量。接下来 N-1 行描述树枝的信息。 每行 3 个整数，前两个是它连接的结点的编号。第 3 个数是这根树枝上苹果的数量。 每根树枝上的苹果不超过 30000 个。
输出格式：
一个数，最多能留住的苹果的数量。
输入样例：
5 2 1 3 1 1 4 10 2 3 20 3 5 20
输入样例：
21
代码实现
import java
.util
.ArrayList
;
import java
.util
.Scanner
;
public class Main {
public Main() {
Scanner sc
=new Scanner(System
.in
);
int N
,Q
; N
=sc
.nextInt(); Q
=sc
.nextInt();
int[][] Mat
=new int[N
+1][N
+1];
for(int i
=1;i
<=N
;i
++)
for(int j
=1;j
<=N
;j
++)
Mat
[i
][j
]=-1;
for(int i
=0;i
<N
-1;i
++) {
int x
,y
,weight
; x
=sc
.nextInt(); y
=sc
.nextInt(); weight
=sc
.nextInt();
Mat
[x
][y
]=Mat
[y
][x
]=weight
;
}
boolean[] Mark
=new boolean[N
+1];
ArrayList
[] Children
=new ArrayList[N
+1];
for(int i
=1;i
<=N
;i
++) Children
[i
]=new ArrayList<Integer>();
ArrayList
<Integer> Que
=new ArrayList<Integer>();
Que
.add(1); Mark
[1]=true; int front
=0;
while(front
<Que
.size()) {
int head
=Que
.get(front
); front
++;
for(int j
=1;j
<=N
;j
++)
if(Mat
[head
][j
]!=-1 && Mark
[j
]==false) {
Que
.add(j
); Mark
[j
]=true;
Children
[head
].add(j
);
}
}
int[][] Apple
=new int[N
+1][Q
+1];
for(int i
=Que
.size()-1;i
>=0;i
--) {
int a
=Que
.get(i
);
if(Children
[a
].size()!=0)
for(int q
=1;q
<=Q
;q
++) {
int max
=0;
int x
=(int) Children
[a
].get(0); int y
=(int) Children
[a
].get(1);
for(int q1
=0;q1
<=q
;q1
++) {
int current
; int q2
=q
-q1
;
if(q1
==0) current
=Apple
[y
][q2
-1]+Mat
[a
][y
];
else {
current
=Apple
[x
][q1
-1]+Mat
[a
][x
];
if(q2
!=0) current
+=Apple
[y
][q2
-1]+Mat
[a
][y
];
}
if(current
>max
) max
=current
;
}
Apple
[a
][q
]=max
;
}
}
System
.out
.println(Apple
[1][Q
]);
}
public static void main(String
[] args
) {
Main main
= new Main();
}
}
