fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #pragma GCC optimize ("O2")
  5. #pragma GCC optimize ("unroll-loops")
  6.  
  7. #include <ext/pb_ds/assoc_container.hpp> 
  8. #include <ext/pb_ds/tree_policy.hpp> 
  9. using namespace __gnu_pbds; 
  10. #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
  11.  
  12. #define ll long long
  13. #define pii pair<ll,ll>
  14. #define fi first
  15. #define sec second
  16. #define ld long double
  17.  
  18. const ll MOD = 1e9 + 7;
  19. const ll N = 2e5 + 5;
  20. const ll INF = 2e18;
  21.  
  22. ll a[N], sz[N], heavy[N], tin[N], dep[N], root[N];
  23. ll up[N][30];
  24.  
  25. vector<ll>adj[N];
  26.  
  27. struct segtree{
  28.     ll n;
  29.     vector<ll>sg;
  30.  
  31.     segtree(ll _n = 0) : n(_n), sg(4 * n + 5) {}
  32.  
  33.     void upd(ll l, ll r, ll cur, ll idx, ll val){
  34.         if(l == r) sg[cur] = val;
  35.         else{
  36.             ll mid = (l + r) / 2;
  37.             if(idx <= mid) upd(l, mid, cur * 2, idx, val);
  38.             else upd(mid + 1, r, cur * 2 + 1, idx, val);
  39.  
  40.             sg[cur] = max(sg[cur * 2], sg[cur * 2 + 1]);
  41.         }
  42.     }
  43.  
  44.     ll query(ll l, ll r, ll cur, ll x, ll y){
  45.         if(l > y || r < x) return -INF;
  46.         if(l >= x && r <= y) return sg[cur];
  47.  
  48.         ll mid = (l + r) / 2;
  49.         return max(query(l, mid, cur * 2, x, y), query(mid + 1, r, cur * 2 + 1, x, y));
  50.     }
  51. } sg(N);
  52.  
  53. void init(ll idx, ll par){
  54.     ll mx = -1;
  55.     heavy[idx] = root[idx] = idx, sz[idx] = 1;
  56.  
  57.     for(auto i : adj[idx]){
  58.         if(i != par){
  59.             dep[i] = dep[idx] + 1;
  60.             up[i][0] = idx;
  61.  
  62.             for(ll bit = 1; bit < 20; bit++){
  63.                 up[i][bit] = up[up[i][bit - 1]][bit - 1];
  64.             }
  65.  
  66.             init(i, idx);
  67.  
  68.             sz[idx] += sz[i];
  69.             if(mx > sz[i]){
  70.                 mx = sz[i];
  71.                 heavy[idx] = i;
  72.             }
  73.         }
  74.     }
  75. }
  76.  
  77. ll t = 0;
  78.  
  79. void build_hld(ll idx, ll par){
  80.     tin[idx] = ++t;
  81.     if(heavy[idx] != idx){
  82.         root[heavy[idx]] = root[idx];
  83.         build_hld(heavy[idx], idx);
  84.     }
  85.  
  86.     for(auto i : adj[idx]){
  87.         if(i != par && i != heavy[idx]){
  88.             build_hld(i, idx);
  89.         }
  90.     }
  91. }
  92.  
  93. ll get_lca(ll a, ll b){
  94.     if(dep[a] < dep[b]) swap(a, b);
  95.  
  96.     ll res = dep[a] - dep[b];
  97.  
  98.     for(ll i = 19; i >= 0; --i){
  99.         if(res & (1LL << i)) a = up[a][i];
  100.     }
  101.  
  102.     if(a == b) return a;
  103.  
  104.     for(ll i = 19; i >= 0; --i){
  105.         if(up[a][i] != up[b][i]) a = up[a][i], b = up[b][i];
  106.     }
  107.  
  108.     return up[a][0];
  109. }
  110.  
  111. ll get(ll a, ll b){
  112.     ll mx = -INF;
  113.     while(a != b){
  114.         if(dep[b] > dep[root[a]]){
  115.             mx = max(mx, sg.query(1, t, 1, tin[a], tin[b]));
  116.             break;
  117.         }
  118.  
  119.         mx = max(mx, sg.query(1, t, 1, tin[root[a]], tin[a]));
  120.         a = up[root[a]][0];
  121.     }
  122.  
  123.     return mx;
  124. }
  125.  
  126. int32_t main(){
  127.     cin.tie(0)->sync_with_stdio(0);
  128.     int tc = 1, cnt = 0;
  129.     // cin >> tc;
  130.     for(;tc; cnt++, tc--){
  131.         ll n,q; cin >> n >> q;
  132.  
  133.         for(int i = 1; i <= n; i++) cin >> a[i];
  134.  
  135.         for(int i = 2; i <= n; i++){
  136.             ll u,v; cin >> u >> v;
  137.             adj[u].push_back(v), adj[v].push_back(u);
  138.         }
  139.  
  140.         init(1, -1);
  141.         build_hld(1, -1);
  142.  
  143.         for(int i = 1; i <= n; i++){
  144.             sg.upd(1, t, 1, tin[i], a[i]);
  145.         }
  146.  
  147.         for(int i = 1; i <= q; i++){
  148.             ll type; cin >> type;
  149.             if(type == 1){
  150.                 ll idx, val; cin >> idx >> val;
  151.                 sg.upd(1, t, 1, tin[idx], val);
  152.             }
  153.             else{
  154.                 ll a,b; cin >> a >> b;
  155.                 ll anc = get_lca(a, b);
  156.  
  157.                 cout << max(get(a, anc), get(b, anc)) << " \n"[i == q];
  158.             }
  159.         }
  160.     }
  161. }
  162.  
  163. /*
  164.  
  165. */
Success #stdin #stdout 0.01s 22560KB
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 4 9 9
https://ideone.com/Rlk3Z3
language:
C++14 (gcc 8.3)
created:
5 hours 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!