背景
\(Luogu\) \(P1122/Codevs5565\)
题意
给定一棵 \(n\) 个节点的以 \(1\) 号点为根节点的树的 \(n-1\) 条边及权值 \((x_i,y_i,w_i)\) ，求砍掉一些枝条后留下 \(q\) 条边的最大边权和。
解法
也不是树形 \(dp\) 模板。还是习题。
由于这棵树是二叉树，有一个优美的性质：某棵子树内保留的树枝只能由左右子树得到（这不是废话吗）。
考虑转换题意，砍掉一些枝条后留下 \(q\) 条边也即留下 \(q+1\) 个点且必须包含根。
于是就可以设 \(f_{x,i}\) 表示以 \(x\) 节点为根的子树留下 \(i\) 个点的最大边权和。
这个时候就要考虑继续转换题目了。由于根必选，所以 \(n-1\) 条边完全可以转化成剩下 \(n-1\) 个点的权值（每个点到它父亲的边的权值）。于是把最大边权和变成了最大点权和。
然后就可以高高兴兴转移了：设节点 \(x\) 的左儿子是 \(l_x\) ，右儿子是 \(r_x\) ，则 \(f_{x,i}=\max_\limits{j \in [0,i-1]} \{ f_{l_x,j}+f_{r_x,i-1-j} \} +val_x\) 。
至于 \(l_x\) 和 \(r_x\) 的求法，见下面的 \(trick\) 吧。
trick
一棵给定 \(n-1\) 条无向边的 \(n(n \leqslant 3 \times 10^3)\) 点有根二叉树左右子节点的求法：
建立邻接矩阵，只不过这次要存成 \(int\) 形式， \(g_{x,y}\) 存的是 \((x,y)\) 的边权。
从根开始建立，自顶向下递归。
每次递归到当前节点 \(x\) 时都遍历 \(n\) 个节点，找到第一个有边权的节点，将其作为 \(l_x\) ，然后递归处理该节点。返回后直接退出循环即可。找 \(r_x\) 时注意要重新遍历 \(n\) 个节点，找到第一个有边权的节点，将其作为 \(r_x\) ，然后递归处理该节点。
细节
注意两个边界： \(f_{x,0}\) 表示选 \(0\) 个节点，答案必然为 \(0\) ； \(l_x=0\) 且 \(r_x=0\) （即 \(x\) 是个叶节点）时没法选子树，直接返回本身权值即可。
代码
\(View\) \(Code\)
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int ret=0,f=1;
char ch=getchar();
while('9'<ch||ch<'0')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while('0'<=ch&&ch<='9')
{
ret=(ret<<1)+(ret<<3)+ch-'0';
ch=getchar();
}
return ret*f;
}
int n,q,x,y,w,g[105][105],val[105],l[105],r[105],f[105][105];
void make_tree(int x)
{
for(register int i=1;i<=n;i++)
{
if(g[x][i]||!g[x][i])
{
val[i]=g[x][i];
g[x][i]=-1;
g[i][x]=-1;
l[x]=i;
make_tree(i);
break;
}
}
for(register int i=1;i<=n;i++)
{
if(g[x][i]||!g[x][i])
{
val[i]=g[x][i];
g[x][i]=-1;
g[i][x]=-1;
r[x]=i;
make_tree(i);
break;
}
}
}
int dp(int x,int cnt)
{
if(!cnt)
return 0;
if((!l[x])&&(!r[x]))
return val[x];
if(f[x][cnt])
return f[x][cnt];
for(register int i=0;i<cnt;i++)
{
f[x][cnt]=max(f[x][cnt],dp(l[x],i)+dp(r[x],cnt-1-i)+val[x]);
}
return f[x][cnt];
}
int main()
{
n=read();
q=read();
memset(g,-1,sizeof(g));
for(register int i=1;i<n;i++)
{
x=read();
y=read();
w=read();
g[x][y]=w;
g[y][x]=w;
}
make_tree(1);
printf("%d\n",dp(1,q+1));
return 0;
}