fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define ld long double
  4. #define endl "\n"
  5. #define task "gia tri cuc dai"
  6. using namespace std;
  7. int n,q,a[200009];
  8. vector<int>ke[200009];
  9. int depth[200009],par[200009],siz[200009],heavy[200009];
  10. void dfs(int u,int prev)
  11. {
  12. 	par[u]=prev;
  13. 	depth[u]=depth[prev]+1;
  14. 	siz[u]=1;
  15. 	int gmax=0;
  16. 	for(auto i:ke[u])
  17. 	{
  18. 		if(prev!=i)
  19. 		{
  20. 			dfs(i,u);
  21. 			if(gmax<siz[i])
  22. 			{
  23. 				heavy[u]=i;
  24. 				gmax=siz[i];
  25. 			}
  26. 			siz[u]+=siz[i];
  27. 		}
  28. 	}
  29. }
  30. int head[200009],pos[200009],tp;
  31. void hld(int u,int acs)
  32. {
  33. 	head[u]=acs;
  34. 	pos[u]=++tp;
  35. 	for(auto i:ke[u]) if(heavy[u]==i) hld(i,acs);
  36. 	for(auto i:ke[u]) if(i!=par[u]&&heavy[u]!=i) hld(i,i);
  37. }
  38. int tree[400009];
  39. void update(int pos,int val)
  40. {
  41. 	pos=n+pos-1;
  42. 	tree[pos]=val;
  43. 	while(pos>1)
  44. 	{
  45. 		pos/=2;
  46. 		tree[pos]=max(tree[pos*2],tree[pos*2+1]);
  47. 	}
  48. }
  49. int get(int l,int r)
  50. {
  51. 	l=n+l-1;
  52. 	r=n+r-1;
  53. 	int res=0;
  54. 	while(l<=r)
  55. 	{
  56. 		if(l%2!=0)
  57. 		{
  58. 			res=max(res,tree[l]);
  59. 			l++;
  60. 		}
  61. 		if(r%2==0)
  62. 		{
  63. 			res=max(res,tree[r]);
  64. 			r--;
  65. 		}
  66. 		l/=2;
  67. 		r/=2;
  68. 	}
  69. 	return res;
  70. }
  71. int query(int x,int y)
  72. {
  73. 	int res=0;
  74. 	while(head[x]!=head[y])
  75. 	{
  76. 		if(depth[head[x]]<depth[head[y]]) swap(x,y);
  77. 		res=max(res,get(pos[head[x]],pos[x]));
  78. 		x=par[head[x]];
  79. 	}
  80. 	if(depth[x]<depth[y]) swap(x,y);
  81. 	res=max(res,get(pos[y],pos[x]));
  82. 	return res;
  83. }
  84. int main()
  85. {
  86.     ios_base::sync_with_stdio(false);
  87.     cin.tie(nullptr);
  88.     cout.tie(nullptr);
  89.     if(fopen(task".inp","r"))
  90.     {
  91.         freopen(task".inp","r",stdin);
  92.         freopen(task".out","w",stdout);
  93.     }
  94.     cin>>n>>q;
  95.     for(int i=1;i<=n;i++) cin>>a[i];
  96.     for(int i=1;i<n;i++)
  97.     {
  98.     	int x,y;
  99.     	cin>>x>>y;
  100.     	ke[x].push_back(y);
  101.     	ke[y].push_back(x);
  102.     }
  103.     dfs(1,0);
  104.     hld(1,1);
  105.     for(int i=1;i<=n;i++) update(pos[i],a[i]);
  106.     while(q--)
  107.     {
  108.     	int type,x,y;
  109.     	cin>>type>>x>>y;
  110.     	if(type==1) update(pos[x],y);
  111.     	else cout<<query(x,y)<<" ";
  112.     }
  113. }
Success #stdin #stdout 0.01s 12936KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/WYEtjk
language:
C++14 (gcc 8.3)
created:
1 day 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!