Dynamic GCD

#include <bits/stdc++.h>

using namespace std;

const int INF = 0x3f3f3f3f3f3f3f3fLL;

int n;
vector<int> tr, tr_sub, a, v;

int timer;
vector<int> sub, h, dad, pos;

vector<vector<int>> gr;

// ------- SegTree -----------
int join(int a, int b) {
  return gcd(a, b);
}

void build_seg(int node, int l, int r) {
  if (l == r) {
    tr[node] = v[l];
    return;
  }
  int lc = node << 1;
  int mid = l + (r - l) / 2;
  build_seg(lc, l, mid);
  build_seg(lc+1, mid+1, r);
}

int query(int node, int l, int r, int idx) {
  if (l == r) return tr[node];
  int lc = node << 1;
  int mid = l + (r - l) / 2;
  if (idx <= mid)
    return tr[node] + query(lc, l, mid, idx);
  else
    return tr[node] + query(lc+1, mid+1, r, idx);
}

void update(int node, int l, int r, int ul, int ur, int val) {
  if (r < l or ur < ul or ur < l or r < ul) return;
  if (ul <= l and r <= ur) {
    tr[node] += val;
    return;
  }
  int lc = node << 1;
  int mid = l + (r - l) / 2;
  update(lc, l, mid, ul, min(mid, ur), val);
  update(lc+1, mid+1, r, max(mid+1, ul), ur, val);
}
// ------- SegTree -----------

// ------- SegTree -----------
void build_sub(int node, int l, int r) {
  if (l == r) {
    tr_sub[node] = l == 1 ? v[l] : v[l] - v[l-1];
    return;
  }
  int lc = node << 1;
  int mid = l + (r - l) / 2;
  build_sub(lc, l, mid);
  build_sub(lc+1, mid+1, r);
  tr_sub[node] = join(tr_sub[lc], tr_sub[lc+1]);
}

void update_sub(int node, int l, int r, int idx, int val) {
  if (l == r) {
    tr_sub[node] += val;
    return;
  }
  int lc = node << 1;
  int mid = l + (r - l) / 2;
  if (idx <= mid)
    update_sub(lc, l, mid, idx, val);
  else
    update_sub(lc+1, mid+1, r, idx, val);
  tr_sub[node] = join(tr_sub[lc], tr_sub[lc+1]);
}

int query_sub(int node, int l, int r, int ql, int qr) {
  // if (r < l or qr < ql or qr < l or r < ql) return 0;
  if (ql <= l and r <= qr) return tr_sub[node];
  int lc = node << 1;
  int mid = l + (r - l) / 2;
  if (qr <= mid) return query_sub(lc, l, mid, ql, min(mid, qr));
  if (mid+1 <= ql) return query_sub(lc+1, mid+1, r, max(mid+1, ql), qr);
  return join(
    query_sub(lc, l, mid, ql, min(mid, qr)),
    query_sub(lc+1, mid+1, r, max(mid+1, ql), qr)
  );
}

void update(int l, int r, int val) {
  update(1, 1, n, l, r, val);
  update_sub(1, 1, n, l, val);
  update_sub(1, 1, n, r+1, -val);
}

int query(int l, int r) {
  if (l == r) {
    return query(1, 1, n, l);
  }
  return join(
    query_sub(1, 1, n, l + 1, r),
    query(1, 1, n, l)
  );
}
// ------- SegTree -----------

// ------- HLD -----------
void dfs(int u, int par = -1) {
  sub[u] = 1;
  for (int &to : gr[u]) if (to != par) {
    dad[to] = u;
    dfs(to, u);
    sub[u] += sub[to];
    if (sub[to] > sub[gr[u][0]] or gr[u][0] == par)
      swap(gr[u][0], to);
  }
}

void build_hld(int u, int par = -1) {
  pos[u] = ++timer;
  v[pos[u]] = a[u];
  for (int to : gr[u]) if (to != par) {
    h[to] = (to == gr[u][0] ? h[u] : to);
    build_hld(to, u);
  }
}

int query_path(int a, int b) {
  if (pos[a] < pos[b]) swap(a, b);

  if (h[a] == h[b]) return query(pos[b], pos[a]);

  return join(query(pos[h[a]], pos[a]), query_path(dad[h[a]], b));
}

void update_path(int a, int b, int d) {
  if (pos[a] < pos[b]) swap(a, b);

  if (h[a] == h[b]) return void(update(pos[b], pos[a], d));

  update(pos[h[a]], pos[a], d);
  update_path(dad[h[a]], b, d);
}
// ------- HLD -----------

int main() {
  cin.tie(0)->sync_with_stdio(0);

  cin >> n;

  gr.assign(n, vector<int>());
  tr.assign(n << 2, 0);
  tr_sub.assign(n << 2, 0);
  a.assign(n, 0);
  v.assign(n + 1, 0);

  sub.assign(n, 0);
  h.assign(n, 0);
  dad.assign(n, -1);
  pos.assign(n, 0);

  for (int i = 0, a, b; i < n-1; ++i) {
    cin >> a >> b;
    gr[a].push_back(b);
    gr[b].push_back(a);
  }

  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }

  dfs(0);
  build_hld(0);

  build_seg(1, 1, n);
  build_sub(1, 1, n);

  int q; cin >> q;
  while (q--) {
    char c; cin >> c;
    if (c == 'F') {
      int a, b; cin >> a >> b;

      cout << abs(query_path(a, b)) << '\n';
    } else {
      int a, b, d; cin >> a >> b >> d;
      if (!d) continue;

      update_path(a, b, d);
    }
  }

}