社区讨论
0分求助,我真的不知道为什么错了
P2015二叉苹果树参与者 2已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @lo1iheyj
- 此快照首次捕获于
- 2023/10/22 21:35 2 年前
- 此快照最后确认于
- 2023/11/02 22:30 2 年前
CPP
#include<bits/stdc++.h>
#define ms(x,v) memset(x,v,sizeof(x));
using namespace std;
const int N = 105;
int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int f[N][N];//维度含义:1.当前节点i,2.砍k条边的最优解
int n, q, head[N], cnt = 1;
struct Edge{
int to, nxt;
}e[N*2];
int val[N], out[N], sz[N];
void addedge( int u , int v ){
e[++cnt].to = v;
e[cnt].nxt = head[u];
head[u] = cnt;
}
void dfs( int u , int fa ){
f[u][0] = val[u];
if( out[u] == 0 ){
sz[u] = 0;
return ;
}
sz[u] = out[u];
for( int i = head[u] ; i ; i = e[i].nxt ){
int v = e[i].to;
if( v != fa )dfs(v,u);
for( int j = min(sz[u],q); j >= 0 ; --j ){
for( int k = 0 ; k <= min(j,sz[v]) ; ++k ){
f[u][j+k] = max(f[u][j+k],f[u][j-1]+f[v][k]);
}
}
if( v != fa )sz[u] += sz[v];
}
}
int main()
{
n = read(), q = read();
int a, b;
for( int i = 1 ; i < n ; ++i ){
a = read(); b = read(); val[i] = read();
addedge(a,b);
addedge(b,a);
out[a]++;
}
dfs(1,0);
for( int i = 1 ; i <= n ; ++i )cout << sz[i] << " ";
cout << f[1][q] << "\n";
return 0;
}
回复
共 4 条回复,欢迎继续交流。
正在加载回复...