Bình luận

• 
  

  1

  kingofgame    12:23 a.m. 29 Tháng 5, 2024

  include <bits/stdc++.h>

  define el '\n'

  define fu(i, a, b) for(long long i = a; i <= b; ++i)

  define fd(i, a, b) for(long long i = a; i >= b; --i)

  define ff first

  define ss second

  define all(v) v.begin(), v.end()

  define mask(i) (1LL << (i))

  define bit(x, i) (((x) >> (i)) & 1)

  define sz(v) (ll) v.size()

  using namespace std;
  using ll = long long;
  using ull = unsigned long long;
  const long long N = 2e5 + 10, mod = 1e9 + 7, base = 29, inf = 1e18;

  mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

  ll Rand(ll l, ll r) {
  return uniform_int_distribution<ll> (l, r) (rng);
  }

  ll last(ll msk) {
  return msk & (-msk);
  }

  ll pop_cnt(ll msk) {
  return __builtin_popcountll(msk);
  }

  ll ctz(ll msk) {
  return __builtin_ctzll(msk);
  }

  ll lg(ll msk) {
  return 63 - __builtin_clzll(msk);
  }

  template <class T1, class T2>
  bool minimize(T1 &a, T2 b) {
  if (a > b) {
  a = b;
  return true;
  }
  return false;
  }

  template <class T1, class T2>
  bool maximize(T1 &a, T2 b) {
  if (a < b) {
  a = b;
  return true;
  }
  return false;
  }

  template <class T>
  void print(T a) {
  for (auto x : a) cout << x << " ";
  cout << el;
  }

  template <class T>
  void compress(vector<T> &a) {
  sort(all(a));
  a.resize(unique(all(a)) - a.begin());
  }

  struct SegmentTree {
  int n;
  vector<int> t;

  SegmentTree(int _n) {
      n = _n;
      t.resize(n * 2 + 10);
  }
  
  void update(int p, int c) {
      p += n;
      t[p] = c;
      while (p) {
          p >>= 1;
          t[p] = max(t[p * 2], t[p * 2 + 1]);
      }
  }
  
  int get(int l, int r) {
      l += n;
      r += n + 1;
      int res = 0;
      while (l < r) {
          if (l & 1) maximize(res, t[l++]);
          if (r & 1) maximize(res, t[--r]);
          l >>= 1;
          r >>= 1;
      }
      return res;
  }
  

  };

  int n, q, timer;
  int id[N], sz[N], par[N], tp[N], h[N], a[N];
  vector<int> adj[N];

  void dfs(int u) {
  sz[u]++;
  for (int v : adj[u]) {
  if (v == par[u]) continue;
  h[v] = h[u] + 1;
  par[v] = u;
  dfs(v);
  sz[u] += sz[v];
  }
  }

  void hld(int u, int root) {
  id[u] = ++timer;
  tp[u] = root;
  int heavy = 0;
  for (int v : adj[u]) {
  if (v == par[u]) continue;
  if (sz[v] > sz[heavy]) heavy = v;
  }
  if (!heavy) return;
  hld(heavy, root);
  for (int v : adj[u]) {
  if (v == par[u] || v == heavy) continue;
  hld(v, v);
  }
  }

  signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> q;
  fu(i, 1, n) cin >> a[i];
  fu(i, 2, n) {
  int u, v;
  cin >> u >> v;
  adj[u].push_back(v);
  adj[v].push_back(u);
  }
  SegmentTree seg(n);
  dfs(1);
  hld(1, 1);
  fu(i, 1, n) seg.update(id[i], a[i]);
  while (q--) {
  int type, u, v;
  cin >> type >> u >> v;
  if (type & 1) {
  seg.update(id[u], v);
  }
  else {
  int res = 0;
  while (tp[u] != tp[v]) {
  if (h[tp[u]] < h[tp[v]]) swap(u, v);
  maximize(res, seg.get(id[tp[u]], id[u]));
  u = par[tp[u]];
  }
  if (h[u] > h[v]) swap(u, v);
  maximize(res, seg.get(id[u], id[v]));
  cout << res << " ";
  }
  }

  }

1 bình luận nữa