fork download
copy 
  1. #pragma GCC optimize("O3,unroll-loops")
  2. #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2")
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5. __attribute__((always_inline)) inline void smax(int& x, int y){
  6.     x > y ? x : (x = y);
  7. }
  8. const int N=2e5+5;
  9. int seg[4*N];
  10. void update(int node,int l,int r,int pos,int val)
  11. {
  12.     if(l>pos||r<pos) return;
  13.     if(l==pos&&r==pos){
  14.         seg[node]=val;
  15.         return;
  16.     }
  17.     int mid=(l+r)>>1;
  18.     if(pos<=mid) update(node*2,l,mid,pos,val);
  19.     else update(node*2+1,mid+1,r,pos,val);
  20.     seg[node]=max(seg[node*2],seg[node*2+1]);
  21. }
  22. int query(int node,int l,int r,int u,int v)
  23. {
  24.     if(l>v||r<u) return 0;
  25.     if(l>=u&&r<=v) return seg[node];
  26.     int mid=(l+r)>>1;
  27.     return max(query(node*2,l,mid,u,v),query(node*2+1,mid+1,r,u,v));
  28. }
  29. int par[N];
  30. vector<int> adj[N];
  31. void dfs_par(int u,int p)
  32. {
  33.     par[u]=p;
  34.     for(auto itr=adj[u].begin();itr!=adj[u].end();itr++){
  35.         if(*itr==p){
  36.             adj[u].erase(itr);
  37.             break;
  38.         }
  39.     }
  40.     for(int v:adj[u]){
  41.         dfs_par(v,u);
  42.     }
  43. }
  44. int sz[N],dep[N];
  45. void dfs_sz(int u){
  46.     //sz[u]=1;
  47.     for(int v:adj[u]){
  48.         dep[v]=dep[u]+1;
  49.         dfs_sz(v);
  50.         sz[u]+=sz[v];
  51.         if(sz[v]>sz[adj[u][0]]) swap(v,adj[u][0]);
  52.     }
  53. }
  54. int cur_tour=1;
  55. int tin[N],nxt[N],tour[N];
  56. void HLD(int u)
  57. {
  58.     tour[cur_tour]=u;
  59.     tin[u]=cur_tour;
  60.     cur_tour++;
  61.     for(int v:adj[u]){
  62.         if(v==adj[u][0]) nxt[v]=nxt[u];
  63.         else nxt[v]=v;
  64.         HLD(v);
  65.     }
  66. }
  67. int A[N];
  68. void build(int node,int l,int r)
  69. {
  70.     if(l==r){
  71.         seg[node]=A[tour[l]];
  72.         return;
  73.     }
  74.     int mid=(l+r)>>1;
  75.     build(node*2,l,mid);
  76.     build(node*2+1,mid+1,r);
  77.     seg[node]=max(seg[node*2],seg[node*2+1]);
  78. }
  79. int query_path(int u,int v,int n)
  80. {
  81.     int ans=0;
  82.     while(nxt[u]!=nxt[v]){
  83.         if(dep[nxt[u]]<dep[nxt[v]]) swap(u,v);
  84.         smax(ans,query(1,1,n,tin[nxt[u]],tin[u]));
  85.         u=par[nxt[u]];
  86.     }
  87.     if(dep[u]>dep[v]) swap(u,v);
  88.     smax(ans,query(1,1,n,tin[u],tin[v]));
  89.     return ans;
  90. }
  91. int main()
  92. {
  93.     ios_base::sync_with_stdio(false);
  94.     cin.tie(0);
  95.     cout.tie(0);
  96.     int n,q;
  97.     cin>>n>>q;
  98.     for(int a=1;a<=n;a++){
  99.         cin>>A[a];
  100.     }
  101.     for(int a=0;a<n-1;a++){
  102.         int x,y;
  103.         cin>>x>>y;
  104.         adj[x].push_back(y);
  105.         adj[y].push_back(x);
  106.     }
  107.     dfs_par(1,1);
  108.     dfs_sz(1);
  109.     nxt[1]=1;
  110.     HLD(1);
  111.     build(1,1,n);
  112.     while(q--){
  113.         int type;
  114.         cin>>type;
  115.         if(type==1){
  116.             int u,val;
  117.             cin>>u>>val;
  118.             update(1,1,n,tin[u],val);
  119.         }
  120.         else{
  121.             int u,v;
  122.             cin>>u>>v;
  123.             cout<<query_path(u,v,n)<<" ";
  124.         }
  125.     }
  126. }
  127.  
Success #stdin #stdout 0.01s 11792KB
comments (?)
stdin
copy 
10 10
9 2 1 1 1 4 2 10 7 4
2 1
3 2
4 2
5 4
6 5
7 6
8 4
9 8
10 2
2 5 4
1 10 4
1 5 9
2 5 4
2 9 5
2 1 10
2 1 6
1 8 4
1 3 5
2 6 1
stdout
copy 
1 9 10 9 9 9
https://ideone.com/jWy57p
language:
C++14 (gcc 8.3)
created:
9 days 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!