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=1e3;
  18. bool check[Max_n+3][Max_n+3];
  19. int a[Max_n+3];
  20. int dem[Max_n+3]; 
  21. ll dp[Max_n+3]; 
  22. int c[Max_n+3];
  23. ll res = -1e18; 
  24. const ll INF = -1e13;
  25. int n ; 
  26. ll ans_dem ;
  27. int vi_tri ; 
  28. int trace[Max_n+3]; 
  29. inline void visit ( int node ){
  30. 	dp[node]= c[node] ;
  31. 	dem[node]++;
  32. 	for (int node_2 = 1 ; node_2 <= n ; node_2 ++ ){
  33. 		if (check[node][node_2]){
  34. 			check[node_2][node] = 0 ; 
  35. 			visit(node_2) ;
  36. 			dp[node] += max ( 0ll , dp[node_2]) ;
  37. 			//dp[node] = max ( 0ll , dp[node]) ;
  38. 			if (dp[node_2]>0 ) dem[node]+=dem[node_2],trace[node_2] = dem[node_2] ;
  39. 		}
  40. 	}
  41. 	//dp[u] += dp[node_2] ;
  42. 	dp[node] = max(0ll,dp[node]) ; 
  43. 	if ( res < dp[node] ){
  44. 		res = dp[node] ;
  45. 		vi_tri = node ;
  46. 		ans_dem = dem[node] ;
  47. 	}
  48. } 
  49. void TRY_VET ( int u , int P ){
  50. 	for (int i = 1 ; i <= n ; i ++ ){
  51. 		if (check[u][i] && trace[i] != 0 ){
  52. 			TRY_VET( i , trace[i] ) ;
  53. 			//P-=trace[i];
  54. 		}
  55. 	}
  56. 	cout << u << ' ';
  57. }
  58. void solve(){
  59. 	cin >> n ; 
  60. 	for (int i = 1 ; i <= n ; i ++ ) cin >> c[i] ;
  61. 	for (int i = 1 ; i < n ; i ++ ){
  62. 		int u , v; cin >> u >> v; 
  63. 		check[u][v] = true ;
  64. 		check[v][u] = true ; 
  65. 	}
  66. 	visit(1) ;
  67. 	cout << res << ' ' << (res!=0?ans_dem:0) << '\n';
  68. 	if (res!=0) TRY_VET(vi_tri , ans_dem) ;
  69. }
  70. _nhatminh{
  71. freopen("");
  72. ios_base::sync_with_stdio(0);
  73. cin.tie(0); cout.tie(0);
  74. int q=1;
  75. // cin >> q;
  76. while (q--)
  77. 	solve();
  78. cerr << '\n' << "Time elapsed " << TIME << "s.\n";
  79. return (0);
  80. }
Success #stdin #stdout #stderr 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 0
stderr
copy 
Time elapsed 0.006698s.
https://ideone.com/cGzrXl
language:
C++14 (gcc 8.3)
created:
4 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!