Codechef Dynamic GCD

//============================================================================
// Name        : ACM
// Author      : Tarango Khan
// Team        : BRACU Byteheads
//============================================================================

#include <bits/stdc++.h>
using namespace std;

/*-------------------------Main code begins now ------------------------------*/
int testnum;
struct LCA {
#include <vector>

    vector<int> L, D;
    vector<vector<int> > P;
    int N;
    LCA(vector<int> dad, vector<int> level) {
        N = dad.size();
        D = dad, L = level;
        int LOG = 1, base = 1;

        while (base < N)
            LOG++, base <<= 1;

        P.resize(N, vector<int>(LOG, -1));

        for (int i = 0; i < N; i++)
            P[i][0] = D[i];

        for (int j = 1; 1 << j < N; j++)
            for (int i = 0; i < N; i++)
                if (P[i][j - 1] != -1)
                    P[i][j] = P[P[i][j - 1]][j - 1];
    }

    int query(int p, int q) {
        int tmp, log, i;
        if (L[p] < L[q])
            tmp = p, p = q, q = tmp;

        for (log = 1; 1 << log <= L[p]; log++)
            ;
        log--;

        for (i = log; i >= 0; i--)
            if (L[p] - (1 << i) >= L[q])
                p = P[p][i];

        if (p == q)
            return p;

        for (i = log; i >= 0; i--)
            if (P[p][i] != -1 && P[p][i] != P[q][i])
                p = P[p][i], q = P[q][i];

        return D[p];
    }
};

int gcd(int a, int b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

struct segment {
    int first, last, diffGcd;
    int lazysum;
};

void addSegment(segment &s1, segment &s2, segment &s3) {
    s3.first = s1.first;
    s3.last = s2.last;
    s3.diffGcd = abs(gcd(s1.diffGcd, gcd(s2.first - s1.last, s2.diffGcd)));
}
void getSegment(int a, segment &s) {
    s.first = s.last = a;
    s.lazysum = 0;
    s.diffGcd = 0;
}

struct segtree {
    int base;
    vector<segment> tree;
    vector<int> A;

    segtree(vector<int> _A) {
        A = _A;
        int N = A.size();
        base = 1;
        while (base < N)
            base *= 2;
        tree.resize(2 * base);
        makeSegment(1);
    }

    void makeSegment(int ind) {
        if (ind >= base)
            getSegment(A[ind - base], tree[ind]);
        else {
            int twice = ind << 1;
            makeSegment(twice);
            makeSegment(twice + 1);
            addSegment(tree[twice], tree[twice + 1], tree[ind]);
            tree[ind].lazysum = 0;
        }
    }

    int lo, hi;

    void update(int ind, int beg, int end, int d) {
        if (end < lo || beg > hi)
            return;
        if (lo <= beg && end <= hi) {
            tree[ind].first += d;
            tree[ind].last += d;
            tree[ind].lazysum += d;
            return;
        }
        int twice = ind << 1, mid = (beg + end) >> 1;

        update(twice, beg, mid, d);
        update(twice + 1, mid + 1, end, d);

        addSegment(tree[twice], tree[twice + 1], tree[ind]);
        tree[ind].first += tree[ind].lazysum;
        tree[ind].last += tree[ind].lazysum;
    }

    int query(int ind, int beg, int end, int lazysum) {
        if (end < lo || beg > hi)
            return 0;
        if (lo <= beg && end <= hi)
            return gcd(tree[ind].first + lazysum, tree[ind].diffGcd);

        lazysum += tree[ind].lazysum;
        int twice = ind << 1, mid = (beg + end) >> 1;

        return gcd(query(twice, beg, mid, lazysum),
                query(twice + 1, mid + 1, end, lazysum));
    }

    void update(int u, int v, int d) {
        lo = u, hi = v;
        update(1, 0, base - 1, d);
    }

    int query(int u, int v) {
        lo = u, hi = v;
        return query(1, 0, base - 1, 0);
    }
};

/*****************************************************************/
const int maxn = 100005;
vector<int> Graph[maxn];
int dad[maxn], subSize[maxn], level[maxn];
int N;

int dfs(int u, int p, int l) {
    if (dad[u] >= 0)
        return 0;
    dad[u] = p;
    level[u] = l;

    int its = 0;
    for (vector<int>::iterator it = Graph[u].begin(); it != Graph[u].end();
            it++) {
        its += dfs(*it, u, l + 1);
    }
    return subSize[u] = 1 + its;
}

int chainNo;
vector<int> chain[maxn];
int chainHead[maxn], chainPos[maxn], chainIndex[maxn];
int A[maxn];

void HLD(int u) {
    if (chain[chainNo].size() == 0){
        chainHead[chainNo] = u;
    }

    chain[chainNo].push_back(u);
    chainPos[u] = chain[chainNo].size() - 1;
    chainIndex[u] = chainNo;

    int most = 0, ind = -1;

    for (vector<int>::iterator it = Graph[u].begin(); it != Graph[u].end();
            it++) {
        int v = *it;
        if (v == dad[u])
            continue;
        if (subSize[v] > most)
            most = subSize[v], ind = v;
    }

    if (ind >= 0)
        HLD(ind);

    for (vector<int>::iterator it = Graph[u].begin(); it != Graph[u].end();
            it++) {
        int v = *it;
        if (v == dad[u] || v == ind)
            continue;
        ++chainNo;
        HLD(v);
    }
}

vector<segtree> decomp;

int hld_find(int u, int l) {
    int soFar = 0;
    while (true) {
        int c = chainIndex[u];

        if (c != chainIndex[l]) {
            soFar = gcd(soFar, decomp[c].query(0, chainPos[u]));
            u = dad[u];
        } else {
            soFar = gcd(soFar, decomp[c].query(chainPos[l], chainPos[u]));
            break;
        }
    }
    return soFar;
}

void hld_change(int u, int l, int d) {
    while (true) {
        int c = chainIndex[u];

        if (c != chainIndex[l]) {
            decomp[c].update(0, chainPos[u], d);
            u = dad[u];
        } else {
            decomp[c].update(chainPos[l], chainPos[u], d);
            break;
        }
    }
}

void solve() {
    memset(dad, -2, sizeof(dad));
    dfs(0, N, 0);
    dad[0] = -1;
    LCA lca(vector<int>(dad, dad + N), vector<int>(level, level + N));
    chainNo = 0;
    HLD(0);
    chainNo++;
    for (int c = 0; c < chainNo; c++) {
        vector<int> its;
        for (vector<int>::iterator it = chain[c].begin(); it != chain[c].end();
                it++) {
            its.push_back(A[*it]);
        }
        decomp.push_back(segtree(its));
    }

    int Q;
    scanf("%d", &Q);
    char cmd[5];
    int u, v, d;
    for (int i = 0; i < Q; i++) {
        scanf("%s", cmd);
        scanf("%d", &u);
        scanf("%d", &v);
        int l = lca.query(u, v);
        if (cmd[0] == 'F') {
            int ans = gcd(hld_find(u, l), hld_find(v, l));
            printf("%d\n", ans);
        }

        else {
            scanf("%d", &d);
            hld_change(u, l, d);
            hld_change(v, l, d);
            hld_change(l, l, -d); // we've added a term of d to lca twice, better remove once.
        }
    }
}

bool input() {
    scanf("%d", &N);
    for (int i = 0; i < N - 1; i++) {
        int a, b;
        scanf("%d", &a);
        scanf("%d", &b);
        Graph[a].push_back(b);
        Graph[b].push_back(a);
    }

    for (int i = 0; i < N; i++)
        scanf("%d", &A[i]);
    return true;
}

int main() {
    int T = 1;
    for (testnum = 1; testnum <= T; testnum++) {
        if (!input())
            break;
        solve();
    }
}