fork(2) download
copy 
  1. /*
  2. 	Milan Bavishi
  3. 	MNNIT Allahbad
  4. 	CSE 2016-2020 batch
  5. */
  6.  
  7.  
  8.  
  9. 				// ¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶ 
  10. 				// ¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶_______________¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶ 
  11. 				// ¶¶¶¶¶¶¶¶¶¶¶_____¶¶¶¶___¶¶¶¶¶¶_____¶¶¶¶¶¶¶¶¶¶¶ 
  12. 				// ¶¶¶¶¶¶¶¶¶___¶¶¶¶¶¶¶______¶¶¶¶¶¶¶¶___¶¶¶¶¶¶¶¶¶ 
  13. 				// ¶¶¶¶¶¶¶___¶¶¶¶¶¶¶¶______¶¶¶_¶¶¶¶¶¶¶¶__¶¶¶¶¶¶¶ 
  14. 				// ¶¶¶¶¶___¶¶¶¶¶¶¶¶¶_______________________¶¶¶¶¶ 
  15. 				// ¶¶¶¶__¶¶¶¶¶¶¶¶¶_________¶¶________¶¶¶¶¶__¶¶¶¶ 
  16. 				// ¶¶¶__¶¶¶¶¶¶¶¶¶¶_________________¶¶¶¶¶¶¶¶__¶¶¶ 
  17. 				// ¶¶__¶¶¶¶¶¶¶¶¶¶¶_____________¶¶¶__¶¶¶¶¶¶¶¶__¶¶ 
  18. 				// ¶¶_¶¶¶¶¶¶¶¶¶¶¶_________¶¶¶¶¶¶¶¶¶_¶¶¶¶¶¶¶¶¶_¶¶ 
  19. 				// ¶__¶¶¶¶¶¶¶¶¶¶¶_________¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶__¶ 
  20. 				// ¶_¶¶¶¶¶¶¶¶¶¶¶¶________¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶_¶ 
  21. 				// ¶_¶¶¶¶¶¶¶¶¶¶¶¶_________¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶_¶ 
  22. 				// ¶_¶¶¶¶¶¶¶¶¶¶¶¶___________¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶_¶ 
  23. 				// ¶_¶¶¶¶¶¶¶¶¶¶¶_____________¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶_¶ 
  24. 				// ¶_¶¶¶¶¶¶¶¶¶¶¶_____¶¶______¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶_¶ 
  25. 				// ¶__¶¶¶¶¶¶¶¶¶______¶¶¶______¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶__¶ 
  26. 				// ¶¶_¶¶¶¶¶¶¶¶¶_____¶¶¶¶¶¶_____¶¶¶¶¶¶¶¶¶¶¶¶¶¶_¶¶ 
  27. 				// ¶¶__¶¶¶¶¶¶¶_____¶¶¶¶¶¶¶¶____¶¶¶¶¶¶¶¶¶¶¶¶¶__¶¶ 
  28. 				// ¶¶¶__¶¶¶¶_______¶¶¶¶¶¶¶¶¶____¶¶¶¶¶¶¶¶¶¶¶__¶¶¶ 
  29. 				// ¶¶¶¶__¶¶_______¶¶¶¶¶¶¶¶¶¶____¶¶¶¶¶¶¶¶¶¶__¶¶¶¶ 
  30. 				// ¶¶¶¶¶__¶______¶¶¶¶¶¶¶¶¶¶¶¶___¶¶¶¶¶¶¶¶¶__¶¶¶¶¶ 
  31. 				// ¶¶¶¶¶¶¶_____¶¶¶¶¶¶¶¶¶¶¶¶¶¶____¶¶¶¶¶¶__¶¶¶¶¶¶¶ 
  32. 				// ¶¶¶¶¶¶¶¶¶__¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶______¶¶___¶¶¶¶¶¶¶¶ 
  33. 				// ¶¶¶¶¶¶¶¶¶¶¶____¶¶¶¶¶¶¶¶¶¶¶¶¶¶_____¶¶¶¶¶¶¶¶¶¶¶ 
  34. 				// ¶¶¶¶¶¶¶¶¶¶¶¶¶¶________________¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶ 
  35. 				// ¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶
  36.  
  37.  
  38.  
  39. #include<bits/stdc++.h>
  40. using namespace std;
  41. // #include <ext/pb_ds/assoc_container.hpp>
  42. // using namespace __gnu_pbds;
  43. // typedef tree<int, null_type, less<int>, rb_tree_tag,
  44. //              tree_order_statistics_node_update>
  45. //     new_data_set;
  46. #define ll long long
  47. #define ld long double
  48. #define ull unsigned long long
  49. #define pii pair<int,int>
  50. #define pll pair<ll,ll>
  51. #define pli pair<ll,int>
  52. #define inf 1e18
  53. #define PB push_back
  54. #define POPB  pop_back
  55. #define pf printf
  56. #define sf scanf
  57. #define ALL(c) c.begin(),c.end()
  58. #define TR(v,it) for(auto it=v.begin();it!=v.end();it++)
  59. #define FT(i,n) for(ll i=0;i<n;i++)
  60. #define FTR(i,n) for(ll i=n;i>=0;i--)
  61. #define FTG(i,a,b) for(ll i=a;i<=b;i++)
  62. #define FTGR(i,a,b) for(ll i=a;i>=b;i--)
  63. #define MP make_pair
  64. #define F first
  65. #define S second
  66. #define endl "\n"
  67. ll mod =1e9+7;
  68. #define err1(x) cout<<"**"<<x<<endl;
  69. #define err2(x,y) cout<<"**"<<x<<" **"<<y<<endl;
  70. #define err3(x,y,z) cout<<"**"<<x<<" **"<<y<<" **"<<z<<endl;
  71. #define TCS int t;cin>>t;while(t--)
  72. #define boost std::ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
  73.  
  74. vector<int> graph[100002];
  75. ll in[100002],out[100002];
  76. int a[100002];
  77. void dfs1(int root,int par)
  78. {
  79. 	in[root]=0;
  80. 	for(int child:graph[root])
  81. 	{
  82. 		if(child==par)continue;
  83. 		dfs1(child,root);
  84.  
  85. 		ll ut=0; 
  86. 		if(a[child]-a[root]>0)
  87. 		ut=a[child]-a[root];
  88.  
  89. 		in[root]=max(in[root],in[child]+ut);
  90. 	}
  91. }
  92.  
  93. void dfs2(int root,int par)
  94. {
  95. 	ll mx1=-1,mx2=-1;
  96. 	ll use;
  97. 	for(int child:graph[root])
  98. 	{
  99. 		if(par==child)continue;
  100. 		use=0;
  101. 		if(a[child]-a[root]>0)use=a[child]-a[root];
  102. 		if(in[child]+use>=mx1)mx2=mx1,mx1=in[child]+use;
  103. 		else if(in[child]+use>mx2)mx2=in[child]+use;
  104. 	}
  105. 	for(int child:graph[root])
  106. 	{
  107. 		if(par==child)continue;
  108. 		use=mx1;
  109. 		ll ut=0;
  110. 		if(a[child]-a[root]>0)
  111. 		ut=a[child]-a[root];
  112. 		if(ut+in[child]==mx1)
  113. 		use=mx2;
  114. 		ut=0;
  115. 		if(a[root]-a[child]>0)ut=a[root]-a[child];
  116. 		out[child]=max(ut+out[root],ut+use);
  117. 		dfs2(child,root);
  118. 	}
  119. }
  120.  
  121. int main()
  122. {
  123. 	#ifndef ONLINE_JUDGE
  124. 		freopen("f.in","r",stdin);
  125. 		freopen("f.out","w",stdout);
  126. 	#endif
  127. 	// ----------------------------------------
  128. 	boost;
  129. 	int n;
  130. 	cin>>n;
  131. 	int q;
  132. 	cin>>q;
  133.  
  134. 	FT(i,n)cin>>a[i];
  135.  
  136. 	int s,d;
  137. 	FT(i,n-1)cin>>s>>d,graph[s].PB(d),graph[d].PB(s);
  138.  
  139. 	dfs1(0,-1);
  140.  
  141. 	dfs2(0,-1);
  142.  
  143. 	while(q--)
  144. 	{
  145. 		cin>>s;
  146. 		cout<<max(in[s],out[s])<<endl;
  147. 	}
  148. 	return 0;
  149. }
Success #stdin #stdout 0s 19536KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/z6llzt
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!