题意：一棵含n个节点的树，保留m条边，使含m条边的子树的边权和最大；
思路：树dp.求含m+1个节点边权和最大的子树。对每个分支节点有三种操作：剪去左子树；剪去右子树；将其节点数合理分配给左右子树；
记以x为根，含k个节点的子树的最大边权和为g[x][k]。
若x为叶节点，则g[x][k]为x通往父节点的边权；若非叶节点，枚举k-1个节点分配在左右子树的所有可能方案，找到最佳方案；
#include#include #include #define N 256#define MAX(a,b) (a>b?a:b)using namespace std;int n,m,ne,x,y,z;//节点数为n,要保留的树枝数为m,边序号为ne,树枝边为（x,y），权为zint id[N],w[N],v[N],next[N],head[N],lch[N],rch[N],f[N];//第i条边的邻接点为id[i],边权为w[i]，后继指针为next[i]，节点x的邻接表指针为head[x],二叉树中节点i的左右儿子lch[i],rch[i]//父亲为f[i],通往父节点的边权为v[i]int g[N][N]; //状态转移方程void add(int x,int y,int z) //将边权为z的树枝边(x,y)加入邻接表{ id[++ne]=y; w[ne]=z; next[ne]=head[x]; head[x]=ne;}void dfs(int x) //从节点x出发，构造二叉树{ for(int p=head[x];p;p=next[p]) //搜索x的所有邻接边p if(id[p]!=f[x]) //若边p的邻接点非x的父亲，则作为x的左或右儿子 { if(!lch[x]) lch[x]=id[p]; else rch[x]=id[p]; f[id[p]]=x;v[id[p]]=w[p]; dfs(id[p]); //x作为边p的邻接点的父亲，设定边权，继续递归边p的邻接点 }}int dp(int x,int k) //从x出发，构造含k个节点且能留住最多苹果数的子树{ if(!k) return 0; if(g[x][k]>=0) return g[x][k]; //返回结果 if(!lch[x]) return (g[x][k]=v[x]); //若x为叶子，则返回x通往父节点的边权 for(int i=0;i