有人吗QAQ
by Geirangerfjard @ 2023-02-23 21:38:48
与根相连的两根树枝至少要留一根
by xiaosi4081 @ 2023-02-25 16:37:45
@[xiaosi4081](/user/343531) 那请问应该怎么改呢
by Geirangerfjard @ 2023-02-27 09:27:09
你如果全部分给右边的话，右边可以有$j-1$条边，而你写了$k-1$，$k-1$是左边的边数-1，是错的
```cpp
#include <iostream>
const int N = 1001;
using namespace std;
int n, q;
int x, y, c, tot;
int h[N], e[N], ne[N], to[N], f[N][N];
int ls[N], rs[N], lapp[N], rapp[N];
//f[i][j] 表示以 i 为根节点 保留 j 根树枝时的最大值
void add(int x, int y, int z)
{
ne[++ tot] = h[x];
h[x] = tot;
e[tot] = z;
to[tot] = y;
}
void build(int x, int fa)//当前节点 父亲节点
{
int cnt = 0;
for (int i = h[x]; i; i = ne[i])
{
int s = to[i];
if (s != fa)
{
cnt ++;
if (cnt == 1) ls[x] = s, lapp[x] = e[i];
else rs[x] = s, rapp[x] = e[i];
build(s, x);
}
}
}
int find(int x, int j)
{
// cout<<x<<" "<<j<<"\n";
if (ls[x] == 0 && rs[x] == 0) return 0;
if (j == 0) return 0;
if (f[x][j] > 0) return f[x][j];
// cout<<f[x][j] <<" "<< x <<" "<<j<<" "<<rapp[x] <<" " << lapp[x] <<"\n";
for (int k = j; k >= 0; k -- )//分配给左儿子的枝数 k
{
// cout<<k<<" ";
// cout<<j<<" ";
// cout<<(k==j ? 1 : 0)<<" ";
// cout<<rs[x]<<" ";
if (k == j) {
f[x][j] = max(f[x][j], find(ls[x], k - 1) + lapp[x]);//全部给右
continue;
}
else if (k == 0){
// cout<<k-1;
// cout<<find(rs[x], j - 1);
f[x][j] = max(f[x][j], find(rs[x] , j -1) + rapp[x]);//全部给左
}
else if(k != j && k != 0){
f[x][j] = max(f[x][j], find(ls[x], k - 1) + lapp[x] + find(rs[x], j - k - 1) + rapp[x]);//两边都有
}
}
return f[x][j];
}
int main()
{
cin >> n >> q;
for (int i = 1; i <= n - 1; i ++ )
{
cin >> x >> y >> c;
add(x, y, c);
add(y, x, c);//惊现yxc
}
build(1, 0);
cout << find(1, q) << endl;
}
```
by Linyize257 @ 2023-03-01 17:50:19
@[Linyize257](/user/485014) 过了，感谢奆佬 ~~话说以后能不能@一下，不然看不到信息QAQ~~
by Geirangerfjard @ 2023-03-05 14:26:56
e
by Linyize257 @ 2023-03-06 13:18:35
@[Alone_Helpless](/user/823773) ok
by Linyize257 @ 2023-03-06 13:19:39