2 条题解
-
1黄楚烨 LV 6 @ 2022-8-10 15:26:09
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<cmath> using namespace std; int n,m,a[10000001],s[10000001],dp[505][505],f[505][505],upd[505],upf[505]; int head[10000001],ne[10000001],to[10000001],id; void add(int x,int y){ to[++id]=y,ne[id]=head[x],head[x]=id; to[++id]=x,ne[id]=head[y],head[y]=id; } void dfs(int u,int fa){ dp[u][0]=f[u][0]=0; dp[u][1]=f[u][1]=a[u]; for(int i=head[u];i;i=ne[i]){ int v=to[i]; if(v==fa) continue; dfs(v,u); for(int j=m;j>=1;j--){ f[u][j]=max(f[u][j],f[v][j-1]); for(int k=j-2;k>=0;k--){ dp[u][j]=max(dp[u][j],dp[v][k]+dp[u][j-k-2]); f[u][j]=max(f[u][j],f[v][k]+dp[u][j-k-1]); f[u][j]=max(f[u][j],dp[v][k]+f[u][j-k-2]); } } } } int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a[i]; } for(int i=1,u,v;i<n;i++){ cin>>u>>v; add(u,v); } dfs(1,0); int ans=0; for(int i=1;i<=m;i++){ ans=max(ans,f[1][i]); } cout<<ans; }
-
-12022-8-10 15:24:19@
/******************** 备注: ********************/ #include <map> #include <queue> #include <stack> #include <math.h> #include <vector> #include <iomanip> #include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> using namespace std; #define LL long long const int N = 1e6+10; const int INF = 0x3f3f3f3f; int n , m , a[N] , s[N] , dp[505][505] , f[505][505] ,upd[505] , upf[505]; int head[N] , to[N] , ne[N] , id; void add(int x , int y) { to[++id] = y , ne[id] = head[x] , head[x] = id; to[++id] = x , ne[id] = head[y] , head[y] = id; } void dfs(int u , int fa) { dp[u][0] = f[u][0] = 0; dp[u][1] = f[u][1] = a[u]; for(int i = head[u] ; i ; i = ne[i]) { int v = to[i]; if(v == fa) continue; dfs(v , u); for(int j = m ; j >= 1 ; j--) { f[u][j] = max(f[u][j] , f[v][j-1]); for(int k = j-2 ; k >= 0 ; k--) { dp[u][j] = max(dp[u][j] , dp[v][k] + dp[u][j-k-2]); f[u][j] = max(f[u][j] , f[v][k] + dp[u][j-k-1]); f[u][j] = max(f[u][j] , dp[v][k] + f[u][j-k-2]); } } } } int main() { cin >> n >> m; for(int i = 1 ; i <= n ; i++) cin >> a[i]; for(int i = 1 , u , v ; i < n ; i++) { cin >> u >> v; add(u , v); } dfs(1 , 0); int ans = 0; for(int i = 1 ; i <= m ; i++) ans = max(ans , f[1][i]); cout << ans << endl; return 0; }
- 1
信息
- ID
- 2643
- 时间
- 3000ms
- 内存
- 61MiB
- 难度
- 7
- 标签
- 递交数
- 83
- 已通过
- 22
- 上传者