fork download
copy 
  1.  
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4.  
  5.  
  6.  
  7. typedef long long int ll;
  8.  
  9. #define endl "\n";
  10. #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  11. #define pb push_back
  12. #define mp make_pair
  13. #define all(c) (c).begin(),(c).end()
  14. #define tr(cont,it) for(decltype((cont).begin()) it = (cont).begin(); it != (cont).end(); it++)
  15. #define present(c,x) ((c).find(x) != (c).end())
  16. #define cpresent(c,x) (find(all(c),x) != (c).end())
  17.  
  18. const ll mod = 1000000007;
  19. const ll inf = (ll)1e15;
  20. ll power(ll a, ll b, ll m = mod) { if(b == 0) return 1; if(b == 1) return (a % m); ll x = power(a, b / 2, m); x = (x*x)%m; if(b % 2) x = (x*a)%m; return x;}
  21.  
  22. const int N=5e5+5;
  23. ll c[N],dp[N];
  24. vector<int> adj[N];
  25. int n;
  26. ll sbts[N];
  27.  
  28. void dfs(int v,int p=-1)
  29. {
  30. 	for(int u : adj[v])
  31. 	{
  32. 		if(u!=p)
  33. 		{
  34. 			dfs(u,v);
  35. 			sbts[v]+=(sbts[u]+1);
  36. 		}
  37. 	}
  38. }
  39. bool cmp(int n1,int n2)
  40. {
  41. 	 return ((2*sbts[n1]-dp[n1])<(2*sbts[n2]-dp[n2])); //returns true if a is ahead of b
  42. }
  43.  
  44. void dfs2(int v,int p=-1)
  45. {
  46. 	for(int u : adj[v])
  47. 	{
  48. 		if(u!=p)
  49. 		{
  50. 			dfs2(u,v);
  51. 		}
  52. 	}
  53. 	sort(adj[v].begin(),adj[v].end(),cmp);
  54. 	dp[v]=c[v];
  55. 	ll add=0;
  56. 	for(int u : adj[v])
  57. 	{
  58. 		if(u==p)
  59. 			continue;
  60. 		dp[v]=max(dp[v],dp[u]+add+1);
  61. 		add+=(sbts[u]);
  62. 	}
  63. }
  64. ll ans=0,trav=0;
  65. void dfs3(int v,int p=-1)
  66. {
  67. 	for(int u : adj[v])
  68. 	{
  69. 		if(u!=p)
  70. 		{
  71. 			trav++;
  72. 			ans=max(ans,trav+c[u]);
  73. 			dfs3(u,v);
  74. 			trav++;
  75. 		}
  76. 	}
  77. }
  78.  
  79. void solve()
  80. {
  81. 	cin >> n;
  82. 	for(int i=1;i<=n;i++)
  83. 		cin >>  c[i];
  84. 	for(int i=1;i<n;i++)
  85. 	{
  86. 		int ui,vi;
  87. 		cin >> ui >> vi;
  88. 		adj[ui].pb(vi);
  89. 		adj[vi].pb(ui);
  90. 	}
  91. 	dfs(1);
  92. 	for(int i=1;i<=n;i++)
  93. 		sbts[i]*=2;
  94. 	dfs2(1);
  95. 	dfs3(1);
  96. 	ans=max(ans,trav+c[1]);
  97. 	cout << ans << endl;
  98.  
  99. }
  100.  
  101. int main()
  102. {
  103. 	IOS;
  104. 	int t = 1, num = 1;   ///// change this t for number of testcase globally
  105.     while (t--) 
  106.     {
  107.         solve();
  108.     }
  109. 	return 0;
  110. }
  111.  
Success #stdin #stdout 0s 38672KB
comments (?)
stdin
copy 
6
1 8 9 6 3 2
1 3
2 3
3 4
4 5
4 6
stdout
copy 
11
https://ideone.com/mldzH0
language:
C++14 (gcc 8.3)
created:
5 years 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!