fork download
copy 
  1. //****** @mdazmat9 **********
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define ll long long
  5. #define int long long
  6. #define UB upper_bound
  7. #define LB lower_bound
  8. #define BS binary_search
  9. #define EB emplace_back
  10. #define PB push_back
  11. #define endl "\n"
  12. #define MOD 1000000007
  13. #define MOD2 998244353
  14. #define F first
  15. #define S second
  16. #define ALL(a) (a).begin(),(a).end()
  17. typedef pair<int, int> pr;
  18. typedef vector<int> VI;
  19. typedef vector<pr> VP;
  20. typedef vector<string> VS;
  21. typedef vector<vector<int>> VV;
  22. #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
  23. #define trace1(x)                cout<<#x<<": "<<x<<endl
  24. #define trace2(x, y)             cout<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
  25. #define trace3(x, y, z)          cout<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
  26. #define trace4(a, b, c, d)       cout<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
  27. #define trace5(a, b, c, d, e)    cout<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
  28. #define trace6(a, b, c, d, e, f) cout<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
  29. #define trace(v) for(auto it=v.begin();it!=v.end();it++)cout<<*it<<" ";cout<<endl;
  30. const int inf = 1e17;
  31. const int MAXN = 200001;
  32. int fast_pow(int x, int y, int p);
  33.  
  34. int ans = 0;
  35. VI g[MAXN];
  36. VI a(MAXN);
  37. VI dp(MAXN); // Stores sum of value of subtree including current node
  38.  
  39. void dfs1(int pos = 1,int pr = 0){
  40. 	dp[pos] = a[pos];
  41. 	for(auto x: g[pos]){
  42. 		if(x!=pr){
  43. 			dfs1(x,pos);
  44. 			dp[pos] += dp[x];
  45. 		}
  46. 	}
  47. }
  48.  
  49. void dfs2(int pos = 1, int pr = 0 , int upper = 0){
  50.  
  51. 	priority_queue<int,VI,greater<int>> pq;
  52. 	if(pr){
  53. 		upper = upper + dp[pr] - dp[pos];
  54. 		pq.emplace(upper);
  55. 	}
  56.  
  57. 	for(auto x:g[pos]){
  58. 		if(x==pr)continue;
  59. 		pq.emplace(dp[x]);
  60. 		dfs2(x,pos,upper);
  61. 		if(pq.size()==3){
  62. 			pq.pop();
  63. 		}
  64. 	}
  65. 	if(pq.size()==2){
  66. 		int op1 = pq.top();pq.pop();
  67. 		int op2 = pq.top();
  68. 		ans = max(ans,op1+op2);
  69. 	}
  70. }
  71.  
  72.  
  73. void solve() {
  74. 	int n;cin>>n;
  75. 	for(int i=1;i<=n;i++)cin>>a[i];
  76. 	for(int i=0;i<n-1;i++){
  77. 		int x,y;cin>>x>>y;
  78. 		g[x].EB(y);
  79. 		g[y].EB(x);
  80. 	}
  81. 	dfs1();
  82. 	dfs2();
  83. 	cout<<ans<<endl;
  84. }
  85.  
  86.  
  87. int32_t main() {
  88. #ifndef ONLINE_JUDGE
  89. 	freopen("input.txt", "r", stdin);
  90. 	freopen("output.txt", "w", stdout);
  91. #endif
  92. 	IOS;
  93. 	int test = 1;
  94. 	// cin>>test;
  95. 	for (int i = 1; i <= test; i++) {
  96.         // cout<<"Case #"<<i<<": ";
  97. 		solve();
  98. 	}
  99. 	return 0;
  100. }
  101. int fast_pow(int x, int y, int p) {
  102. 	int res = 1;
  103. 	x = x % p;
  104. 	while (y > 0) {
  105. 		if (y & 1)
  106. 			res = (res * x) % p;
  107. 		y = y >> 1;
  108. 		x = (x * x) % p;
  109. 	}
  110. 	return res;
  111. }
Runtime error #stdin #stdout 0s 11148KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/7oIiwK
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!