fork download
copy 
  1. #pragma GCC optimize("Ofast")
  2. #pragma GCC optimize("unroll-loops")
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5. // #define int long long
  6. #define fi first
  7. #define se second
  8. #define siz(x) (int)(x.size())
  9. #define all(x) x.begin(), x.end()
  10. #define debug_arr(x,len) for(int _=1; _<=len; _++) cout<<x[_]<<" "; cout<<'\n';
  11. #define debug(x) cout<<'\n'<<#x<<": "<<x<<'\n';
  12. const int maxN = 5e3+5;
  13.  
  14. int n, a[maxN], dp[maxN][maxN], sz[maxN];
  15. vector<int>adj[maxN];
  16.  
  17. void pre_dfs(int u, int v)
  18. {
  19. 	sz[u] = 1;
  20. 	for(auto i: adj[u])
  21. 	{
  22. 		if(i == v) continue;
  23. 		pre_dfs(i, u);
  24. 		sz[u] += sz[i];
  25. 	}
  26. }
  27. void dfs(int u, int v)
  28. {
  29. 	int tmp = 1;
  30. 	for(auto i: adj[u])
  31. 	{
  32. 		if(i == v) continue;
  33. 		dfs(i, u);
  34. 		vector<int>ans(n+1, -1e9);
  35. 		for(int j=1; j<=tmp; j+=1)
  36. 		{
  37. 			for(int k=1; k<=sz[i]; k+=1)
  38. 			{
  39. 				if(j + k > n) continue;
  40. 				if(dp[u][j] == -1e9) continue;
  41. 				if(dp[i][k] == -1e9) continue;
  42. 				ans[j+k] = max({ans[j+k], dp[u][j+k], dp[u][j]+dp[i][k]});
  43. 			}
  44. 		}
  45. 		for(int j=1; j<=n; j+=1) dp[u][j] = max(dp[u][j], ans[j]);
  46. 		tmp += sz[i];
  47. 	}
  48. }
  49.  
  50. void solve()
  51. {
  52.  
  53. }
  54.  
  55. int32_t main()
  56. {
  57. 	ios_base::sync_with_stdio(0); cin.tie(0);
  58. 	cin>>n;
  59. 	for(int i=1; i<=n; i+=1) cin>>a[i];
  60. 	for(int i=1; i<n; i+=1)
  61. 	{
  62. 		int x,y; cin>>x>>y;
  63. 		adj[x].push_back(y);
  64. 		adj[y].push_back(x);
  65. 	}
  66. 	for(int i=1; i<=n; i+=1)
  67. 	{
  68. 		for(int j=1; j<=n; j+=1) dp[i][j] = -1e9;
  69. 		dp[i][0] = 0;
  70. 		dp[i][1] = a[i];
  71. 	}
  72. 	pre_dfs(1,0);
  73. 	dfs(1, 0);
  74. 	for(int i=1; i<=n; i+=1)
  75. 	{
  76. 		int res = -1e9;
  77. 		for(int j=1; j<=n; j+=1) res = max(res, dp[j][i]);
  78. 		cout<<res<<" ";
  79. 	}
  80. }
  81.  
  82. // dp[i][j] la ans max voi tplt co j node, o trong subtree i va co chua i;
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/qhYFZK
language:
C++14 (gcc 8.3)
created:
7 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!