fork download
copy 
  1. //It's all about what U BELIEVE
  2. #include<map>
  3. #include<set>
  4. #include<stack>
  5. #include<queue>
  6. #include<deque>
  7. #include<cmath>
  8. #include<bitset>
  9. #include<vector>
  10. #include<cstring>
  11. #include<stdio.h>
  12. #include<iostream>
  13. #include<algorithm>
  14. #define endl '\n'
  15. #define PI acos(-1)
  16. #define INF ~(1<<31)
  17. #define pb push_back
  18. #define pob pop_back
  19. #define wtm while(t--)
  20. #define wnm while(n--)
  21. #define MOD 1000000007
  22. #define lsone(Z) (Z&-Z)
  23. #define gcu getchar_unlocked
  24. #define allof(Z) Z.begin(),Z.end()
  25. #define rallof(Z) Z.rbegin(),Z.rend()
  26. #define mset(z,v) memset(z,v,sizeof(z))
  27. #define lne if(line)puts("");else line =1
  28. #define fo(s,y,z) for(int y=s ; y<(int)z ; y++)
  29. #define readf freopen("/home/ebram96/Desktop/in" , "r" , stdin);
  30. #define writef freopen("/home/ebram96/Desktop/out" , "w" , stdout);
  31. using namespace std;
  32. typedef unsigned long long ull;
  33. typedef pair<ull,ull> pairull;
  34. typedef pair<int,int> pairii;
  35. typedef vector<string> vstr;
  36. typedef deque<int> dqint;
  37. typedef set<ull> setull;
  38. typedef unsigned int ui;
  39. typedef queue<int> qint;
  40. typedef vector<int> vi;
  41. typedef set<int> seti;
  42. typedef long long ll;
  43. //int dx[]={-1,0,1, 0,-1,1, 1,-1};
  44. //int dy[]={ 0,1,0,-1, 1,1,-1,-1};
  45. ll subTreeSum[200001];
  46. vi adj[200001];
  47. int n , a[200001] , root_parent = 1;
  48. int getRoot(int node,int p)
  49. {
  50. 	int sz = adj[node].size();
  51. 	if(sz > 2)
  52. 	{
  53. 		root_parent = p;
  54. 		return node;
  55. 	}
  56. 	fo(0,y,sz)if(adj[node][y] != p)
  57. 		return getRoot(adj[node][y],node);
  58. 	return 1;
  59. }
  60. pair<ll,ll> dfs(int node,int p)
  61. {
  62. 	ll sum = 0 , mx = -1e17;
  63. 	pair<ll,ll>subtree;
  64. 	int sz = adj[node].size();
  65. 	fo(0,y,sz)if(adj[node][y] != p)
  66. 	{
  67. 		subtree = dfs(adj[node][y],node);
  68. 		sum += subtree.first;
  69. 		mx = max(mx , subtree.second);
  70. 	}
  71. 	subTreeSum[node] = (mx != -1e17 ? max(mx , sum+a[node]) : a[node]);
  72. 	return {sum+a[node],subTreeSum[node]};
  73. }
  74. int main()
  75. {
  76. 	//readf
  77. 	scanf("%d",&n);
  78. 	fo(1,y,n+1)scanf("%d",&a[y]);
  79. 	int u , v;
  80. 	fo(0,y,n-1)
  81. 	{
  82. 		scanf("%d %d",&u,&v);
  83. 		adj[u].pb(v);
  84. 		adj[v].pb(u);
  85. 	}
  86. 	int root = 1 , sz = adj[1].size();
  87. 	/*         4
  88. 	 *        /
  89. 	 * 1--2--3
  90. 	 *        \
  91. 	 *         5
  92. 	 *
  93. 	 *  root = 3 , root_parent = 2
  94. 	 */
  95. 	if(sz==1)
  96. 		root = getRoot(1,1);
  97. 	ll res1 = -1e17 , res2 = -1e17;
  98. 	dfs(root,root_parent);
  99. 	sz = adj[root].size();
  100. 	fo(0,y,sz)if(adj[root][y] != root_parent)
  101. 		if(subTreeSum[adj[root][y]] > res1)
  102. 		{
  103. 			res2 = res1;
  104. 			res1 = subTreeSum[adj[root][y]];
  105. 		}
  106. 		else if(subTreeSum[adj[root][y]] > res2)
  107. 			res2 = subTreeSum[adj[root][y]];
  108. 	if(res2 == -1e17)
  109. 		puts("Impossible");
  110. 	else
  111. 		printf("%lld",res1+res2);
  112. }
  113.  
Success #stdin #stdout 0s 7776KB
comments (?)
stdin
copy 
8
0 5 -1 4 3 2 6 5
1 2
2 4
2 5
1 3
3 6
6 7
6 8
stdout
copy 
25
https://ideone.com/fWLX8s
language:
C++14 (gcc 8.3)
created:
6 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!