fork(3) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. ll M=300000;
  5. vector<ll> g[300000];
  6. ll  in[300000], out[300000];
  7. void dfs1(ll u, ll par,ll A[]){
  8. 	in[u] = 0;
  9. 	for(ll v:g[u]){
  10. 		if (v == par) continue;
  11. 		dfs1(v, u,A);
  12. 		ll tu=0;
  13. 		if ((A[v]-A[u])>0)
  14. 		tu=(A[v]-A[u]);
  15. 		in[u] = max(in[u], tu+in[v]);
  16. 	}
  17. }
  18. void dfs2(ll u, ll par,ll A[]){
  19. 	ll mx1(-1), mx2(-1);
  20.     //find top 2 maximum values of in[v]
  21.     for(ll v: g[u]){
  22.             if(v == par) continue;
  23.             ll tu=0;
  24.     		if ((A[v]-A[u])>0)
  25.     		tu=(A[v]-A[u]);
  26.             if(in[v]+tu >= mx1) mx2 = mx1, mx1 = in[v]+tu;
  27.             else if(in[v]+tu > mx2) mx2 = in[v]+tu;
  28.     }
  29. 	for(ll v:g[u]){
  30. 		if (v == par) continue;
  31. 		ll use = mx1;
  32. 		ll tu=0;
  33. 		if ((A[u]-A[v])>0)
  34. 		tu=(A[u]-A[v]);
  35. 		ll tu2=0;
  36.     	if ((A[v]-A[u])>0)
  37.     		tu2=(A[v]-A[u]);
  38. 		if(mx1 == in[v]+tu2) 
  39. 			use = mx2;
  40. 		out[v] = max(tu+out[u], tu+use);
  41. 		//cout<<v<<" "<<use<<endl;
  42. 		dfs2(v, u,A);
  43. 	}
  44. }
  45. int main()
  46. {
  47. 	ll N,Q;
  48. 	cin>>N>>Q;
  49. 	ll A[N];
  50. 	for(ll i=0;i<N;i++)
  51. 	cin>>A[i];
  52. 	ll n=N-1;
  53. 	ll a,b;
  54. 	while(n--)
  55. 	{
  56. 		cin>>a>>b;
  57. 		//a--;b--;
  58. 		g[a].push_back(b);
  59. 		g[b].push_back(a);
  60. 	}
  61. 	dfs1(0,-1,A);
  62. 	out[0]=0;
  63. 	dfs2(0,-1,A);
  64. 	while(Q--){
  65. 	 cin>>a;
  66. 	 //a--;
  67. 	cout<<max(in[a],out[a])<<endl;
  68. 	}
  69. } 
  70.  
  71.  
Success #stdin #stdout 0.01s 10180KB
comments (?)
stdin
copy 
6 6
1 2 3 4 5 4
1 0
1 2
1 3
3 4
4 5
0
1
2
3
4
5
stdout
copy 
4
3
3
1
1
2
https://ideone.com/od5toC
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!