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 << " ";
  }
  }

  }

• 
  

  0

  N7hoatt    5:01 p.m. 29 Tháng 8, 2023

  Cho một cây gồm \(n\) đỉnh. Các đỉnh được đánh số từ \(1,2,3\dots,n\) và đỉnh \(1\) là gốc của cây. Mỗi đỉnh có một giá trị.

  Hãy thực hiện \(q\) truy vấn có dạng:

  1. Thay đổi giá trị đỉnh \(s\) thành \(x\).
  2. Tìm giá trị lớn nhất trên đường đi từ đỉnh \(a\) tới đỉnh \(b\).

  Input

  • Dòng đầu tiên gồm hai số nguyên \(n\), \(q\): số lượng đỉnh và số lượng truy vấn. Các đỉnh được đánh số từ \(1,2,3,\dots,n\).
  • Dòng tiếp theo gồm \(n\) số nguyên \(v_1,v_2,v_3,\dots,v_n\): giá trị của từng đỉnh.
  • \(n-1\) dòng sau đó biểu diễn các cạnh. Mỗi dòng gồm hai số nguyên \(a\) và \(b\): có cạnh nối giữa \(a\) và \(b\).
  • \(q\) dòng cuối cùng biểu diễn các truy vấn. Mỗi truy vấn có dạng "1 s x" hoặc "2 a b"

  Output

  • In ra kết quả cho truy vấn loại 2.

  Constraints

  • \(1\leq n,q\leq 2 \times 10^5\).
  • \(1\leq a,b,s\leq n\).
  • \(1\leq v_i, x\leq 10^9\).

  Example

  Test

  Input

  5 3
  2 4 1 3 3
  1 2
  1 3
  2 4
  2 5
  2 3 5
  1 2 2
  2 3 5

  Output

  4 3

  Note
  1 phản hồi