fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define _nhatminh  int main()
  3. #define ll long long
  4. #define str string
  5. #define fir first
  6. #define sec second
  7. #define ld long double
  8. #define pb push_back
  9. #define MOD 100000009
  10. #define freopen(name) if(fopen(name".INP","r")) {freopen (name".INP","r",stdin); freopen (name".OUT","w",stdout);}
  11. #define ALL(x) (x).begin(),(x).end()
  12. #define piint pair < int , int >
  13. #define piL pair < int , ll>
  14. #define pLL pair < ll , ll >
  15. #define TIME (1.0*clock()/CLOCKS_PER_SEC)
  16. using namespace std;
  17. const int Max_n=200;
  18. bool a[Max_n+3][Max_n+3];
  19. ll d[Max_n+3][Max_n+3];
  20. int c[Max_n+3];
  21. int trace[Max_n+3][Max_n+3];
  22. int n , p ; 
  23. const int INF = -1e9 ;
  24. void visit ( int node ){
  25. 	d[node][1] = c[node];
  26. 	d[node][0] = 0 ;
  27. 	for (int node_2 = 1 ; node_2 <= n ; node_2 ++ ){
  28. 		if (a[node][node_2]){
  29. 			a[node_2][node] = 0 ;
  30. 			visit(node_2) ;
  31. 			for (int i = p ; i >= 1 ; i -- )
  32. 				for (int j = 1 ; j < i ; j ++){
  33. 					// i - j + j = i
  34. 					if (d[node][i] < (d[node][j] + d[node_2][i-j])){
  35. 						d[node][i] = d[node][j] + d[node_2][i-j] ;
  36. 						trace[node_2][i] = i - j ;
  37. 					}
  38. 				}
  39. 		}
  40. 	}
  41. }
  42. int TIM_MAX(){
  43. 	ll res = 1 , ans = d[1][p];
  44. 	for (int i = 2  ; i <= n ; i ++ ){
  45. 		if (d[i][p] > ans ){
  46. 			ans = d[i][p];
  47. 			res = i ;
  48. 		}
  49. 	}
  50. 	return res ; 
  51. }
  52. void ANS (int node , int P ){
  53. 	for (int node_2 = n ; node_2 >= 1 ; node_2 -- ){
  54. 		if ( a[node][node_2] && trace[node_2][P]>0) {
  55. 			ANS(node_2,trace[node_2][P]),P-=trace[node_2][P];
  56. 			//cout << P << '\n';
  57. 		}
  58. 	}
  59. 	cout << node << ' ' ;
  60. }
  61. void solve(){
  62. 	cin >> n >> p ;
  63. 	for (int i = 1 ; i <= n ; i ++ ) cin >> c[i] ;
  64. 	for (int i = 2 ; i <= n ; i ++ ){
  65. 		int u , v; cin >> u >> v;
  66. 		a[u][v] = 1 ;
  67. 		a[v][u] = 1 ;
  68. 	}
  69. 	memset(d , INF , sizeof(d));
  70. 	visit(1);
  71. 	int t = TIM_MAX();
  72. 	ANS(t,p);
  73. 	//cout << t << ' ' << d[t][p] << '\n';
  74. }
  75. _nhatminh{
  76. freopen("");
  77. ios_base::sync_with_stdio(0);
  78. cin.tie(0); cout.tie(0);
  79. int q=1;
  80. // cin >> q;
  81. while (q--)
  82. 	solve();
  83. cerr << '\n' << "Time elapsed " << TIME << "s.\n";
  84. return (0);
  85. }
Success #stdin #stdout #stderr 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
stderr
copy 
Time elapsed 0.004917s.
https://ideone.com/IDGGrF
language:
C++14 (gcc 8.3)
created:
5 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!