Description
Let's imagine how apple tree looks inbinary computer world. You're right, it looks just like a binary tree, i.e. anybiparous branch splits up to exactly two new branches. We will
enumerate byintegers the root of binary apple tree, points of branching and the ends oftwigs. This way we may distinguish different branches by their ending points.We will assume
that root of tree always is numbered by 1 and all numbers usedfor enumerating are numbered in range from 1 to N, where N is the total numberof all enumerated points. For
instance in the picture below N is equal to 5.Here is an example of an enumerated tree with four branches:
2 5
\ /
3 4
\/
1
As you may know it's not convenient to pickan apples from a tree when there are too much of branches. That's why some ofthem should be removed from a tree. But you are
interested in removing branchesin the way of minimal loss of apples. So your are given amounts of apples on abranches and amount of branches that should be preserved. Your
task is todetermine how many apples can remain on a tree after removing of excessivebranches.
Input
First line of input contains two numbers: Nand Q (2 ≤ N ≤ 100; 1 ≤ Q ≤ N − 1). N denotes the number of enumerated points in a tree. Qdenotes amount of branches that should be
preserved. Next N − 1 lines containsdescriptions of branches. Each description consists of a three integer numbersdivided by spaces. The first two of them define branch by it's
ending points.The third number defines the number of apples on this branch. You may assumethat no branch contains more than 30000 apples.
Output
Output should contain the only number —amount of apples that can be preserved. And don't forget to preserve tree'sroot ;-)
SampleInput
5 2
1 3 1
1 4 10
2 3 20
3 5 20
SampleOutput
21
题目大意：
有一颗拥有n关系的带权二叉树要剪去q根枝条求整棵树的最大权值和。
思路：
因为是求最优值所以想到dp，因为是赤裸裸的二叉树所以想到赤裸裸的树状dp，因为是赤裸裸的树状dp所以放上赤裸裸的状态转移方程。
f[i,j]:=max(f[i.left,k]+a[I,i.left],f[i.right,j-k]+a[I,i.right]),0<=k<=j
其中f[I,j]表示以i为根节点，剪去j根枝条的最优值，a[I,j]表示连接I、j枝条上的权值。F[1,q]即所求答案。注意要在开始转换成一颗二叉树。
源代码/pas
typetree=record l,r:longint;end;var n,q:longint; a,f,v:array[0..100,0..100]of longint; t:array[0..100]of tree;function max(x,y:longint):longint;begin if x>y then max:=x else max:=y;end;procedure init;var i,x,y,z:longint;begin readln(n,q); for i:=1 to n-1 do begin readln(x,y,z); a[x,y]:=z; a[y,x]:=z; v[x,y]:=1; v[y,x]:=1; end;end;procedure create(x:longint);var i:longint;begin for i:=1 to n do if (v[x,i]<>0) then begin if (t[x].l=0) then t[x].l:=i else if (t[x].r=0) then t[x].r:=i; v[i,x]:=0; v[x,i]:=0; create(i); end;end;procedure dp;var i,j,k:Longint;begin for i:=1 to n do f[i,1]:=max(a[i,t[i].l],a[i,t[i].r]); for j:=2 to q do for i:=1 to n do begin f[i,j]:=max(a[i,t[i].r]+f[t[i].r,j-1],a[i,t[i].l]+f[t[i].l,j-1]); for k:=0 to j-2 do f[i,j]:=max(f[i,j],f[t[i].l,k]+f[t[i].r,j-2-k]+a[i,t[i].l]+a[i,t[i].r]); end;end;begin init; create(1); dp; writeln(f[1,q]);end.