**题目描述** 有一棵苹果树，如果树枝有分叉，一定是分$2$叉（就是说没有只有$1$个儿子的结点） 这棵树共有$N$个结点（叶子点或者树枝分叉点），编号为$1∼N$,树根编号一定是$1$。 我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有$4$个树枝的树 ```livescript 2 5 \ / 3 4 \ / 1 ``` 现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。 给定需要保留的树枝数量，求出最多能留住多少苹果。 **输入格式：** 第一行$2$个整数，$N$和$Q$分别表示表示树的结点数，和要保留的树枝数量。 接下来$N-1$行，每行$3$个整数，描述一根树枝的信息：前$2$个数是它连接的结点的编号，第$3$个数是这根树枝上苹果的数量。 **输出格式：** 一个数，最多能留住的苹果的数量。 **输入样例#1：** 5 2 1 3 1 1 4 10 2 3 20 3 5 20 **输出样例#1： ** 21 **说明/提示** $1\leq Q <N\leq 100$，每根树枝上的苹果 $\leq 3\times 10^4$。 这道题有个很大的坑。由于所给的数据只表明了两个点相连，并没有说哪个是父节点哪个是子节点。所以我建了一个邻接表，并把每个数据建两个边。这样子节点一定有一条边连接到父节点，具体是第几条边由建表的方式和输入数据的先后决定。在样例数据中，连接到父节点的这条边都是子节点的最后一条边，所以对于二叉树来说，只把前两条边拿出来，并不影响结果。但是其他的测试数据中，连接到父节点的边很可能不是最后一个，这样就会导致结果错误。所以在动归的过程中，要判断由子节点搜到的点是不是父节点，如果是，要跳过这条边，那么下一个就一定是子节点的子节点。 代码： ```cpp #include <iostream> #define MAX_N 1000 using namespace std; struct type { int adjvex,nextarc; long int value; } edge[MAX_N]; int cnt,head[MAX_N],father[MAX_N]; long int dp[MAX_N][MAX_N],value[MAX_N]; //dp[root][num]表示以root为根节点的子树保留num个节点的最大值 void AddEdge(int x,int y,long int v) { ++cnt; edge[cnt].nextarc=head[x];//next指向下一条边 edge[cnt].adjvex=y;//adjvex为当前边的终点 head[x]=cnt;//当前边被设为顶点x的第一条边 edge[cnt].value=v; } void TDP(int root,int num) { if(num==0)//不保留枝条 dp[root][num]=0; else if(edge[head[root]].nextarc==0)//该节点为叶子节点 dp[root][num]=value[root]; else { //father数组保存子节点的父节点 //因为该二叉树由无向图得来，子节点可以通过边搜到父节点 //以下过程用来跳过子节点连接父节点的那条边 //这条边可能出现在子节点所连接边的任何一个位置，有添加边的顺序决定 int arc=head[root];//arc为root节点的第一条边 if(edge[arc].adjvex==father[root]) //如果arc的终点为root节点的父节点 arc=edge[arc].nextarc;//arc向后走一个，找到下一条边 int lchild=edge[arc].adjvex; //左孩子结点为arc的终点 father[lchild]=root;//左孩子结点的父节点设为root value[lchild]=edge[arc].value; arc=edge[arc].nextarc;//arc再向后走一个，找到下一条边作为root的右孩子节点 if(edge[arc].adjvex==father[root]) //同上，防止该边连到root的父节点 arc=edge[arc].nextarc; int rchild=edge[arc].adjvex; father[rchild]=root; value[rchild]=edge[arc].value; for(int i=0; i<num; ++i) { if(dp[lchild][i]==0) TDP(lchild,i); if(dp[rchild][num-1-i]==0) TDP(rchild,num-1-i); dp[root][num]=max(dp[root][num],dp[lchild][i]+dp[rchild][num-1-i]+value[root]); } } } int main() { int N,Q; cin>>N>>Q; for(int i=0; i<N-1; ++i) { int x,y; long int v; cin>>x>>y>>v; AddEdge(x,y,v);//x,y不确定哪个是父节点那个是子节点 AddEdge(y,x,v); } //由题目知，二叉树根节点一定是1 //Q+1表示保留Q条树枝，即保留Q+1个顶点 TDP(1,Q+1); cout<<dp[1][Q+1]; return 0; } ```