你先康康我的AC代码
```cpp
#include <bits/stdc++.h>
using namespace std;
int n, q, h[105], f[105][105];
struct node {
int v, w, p;
} edge[205];
void add(int u, int v, int w) {
edge[++h[0]].v = v;
edge[h[0]].w = w;
edge[h[0]].p = h[u];
h[u] = h[0];
return ;
}
void dfs(int u, int fa) {
for (int i = h[u]; i; i = edge[i].p) {
int v = edge[i].v;
if (v == fa)
continue;
dfs(v, u);
for (int j = q; j >= 1; j--)
for (int k = 0; k <= j - 1; k++)
f[u][j] = max(f[u][j], f[u][k] + f[v][j - k - 1] + edge[i].w);
}
return ;
}
int main() {
scanf("%d%d", &n, &q);
for (int i = 1; i < n; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
add(u, v, w);
add(v, u, w);
}
dfs(1, 0);
printf("%d", f[1][q]);
return 0;
}
```
by cyb6666 @ 2024-02-12 10:06:15
@[cyb6666](/user/780060) 我改成链式前向星就过了
代码:
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=105;
struct edge{
int next;
int to;
int len;
}e[2*N];
int head[N];
int f[N][N];
int cnt=0;
int ecnt[N];
bool vis[N];
int n,q;
void add(int from,int to,int len){
e[++cnt].to=to;
e[cnt].next=head[from];
e[cnt].len=len;
head[from]=cnt;
}
void dfs(int x){
vis[x]=1;
for(int i=head[x];i;i=e[i].next){
if(!vis[e[i].to]){
int v=e[i].to;
dfs(v);
ecnt[x]+=ecnt[v]+1;
for(int j=min(ecnt[x],q);j>0;j--)
for(int k=min(j-1,ecnt[v]);k>=0;k--)
f[x][j]=max(f[x][j],f[v][k]+f[x][j-k-1]+e[i].len);
}
}
}
int main(){
cin>>n>>q;
for(int i=1;i<n;i++){
int f,t,l;
cin>>f>>t>>l;
add(f,t,l);
add(t,f,l);
}
dfs(1);
cout<<f[1][q];
}
```
但是邻接矩阵就不能过
by useful_algorithms @ 2024-02-13 09:06:34