DFS traversal establishes contiguous intervals for subtrees. When a node u is visited, all nodes within its subtree receive subsequent timestamps. Let entry[u] denote the discovery time and size[u] the subtree node count. The subtree of u perfectly maps to the array segment [entry[u], entry[u] + size[u] - 1]. Subtree modifications and queries thus transform directly into standard range updates and lookups.

int timestamp = 0;
void compute_entry(int u, int p) {
    entry[u] = ++timestamp;
    size[u] = 1;
    for (int v : adj[u]) {
        if (v != p) {
            compute_entry(v, u);
            size[u] += size[v];
        }
    }
}

While DFS order solves subtree problems, path queries between arbitrary nodes require breaking the path into contiguous segments. Heavy-Light Decomposition partitions the tree into vertical chains such that any root-to-leaf path intersects at most O(log N) chains. For each node, its child with the largest subtree is designated the heavy child. The edge connecting them is a heavy edge, while edges to other children are light edges. Consecutive heavy edges form a heavy chain. The decomposition requires two DFS traversals. The first calculates subtree sizes, parent pointers, depths, and identifies heavy children.

void first_dfs(int u, int p) {
    size[u] = 1;
    parent[u] = p;
    depth[u] = depth[p] + 1;
    heavy[u] = -1;
    int max_sz = 0;
    for (int v : adj[u]) {
        if (v != p) {
            first_dfs(v, u);
            size[u] += size[v];
            if (size[v] > max_sz) {
                max_sz = size[v];
                heavy[u] = v;
            }
        }
    }
}

The second traversal assigns DFS timestamps while prioritizing heavy children. This ensures nodes within the same heavy chain receive consecutive timestamps. Each node also records the topmost node of its chain (chain_top[u]).

int cur_pos = 0;
void second_dfs(int u, int p, int top_node) {
    chain_top[u] = top_node;
    entry[u] = ++cur_pos;
    if (heavy[u] != -1) {
        second_dfs(heavy[u], u, top_node);
    }
    for (int v : adj[u]) {
        if (v != p && v != heavy[u]) {
            second_dfs(v, u, v); // Light children start new chains
        }
    }
}

To process a path between u and v, repeatedly jump up the tree from the node whose chain head has a greater depth. For each jump, the segment from the node to its chain head forms a contiguous interval in the DFS order. Once both nodes reside in the same chain, the remaining interval is processed directly.

void modify_path(int u, int v, int delta) {
    while (chain_top[u] != chain_top[v]) {
        if (depth[chain_top[u]] < depth[chain_top[v]]) std::swap(u, v);
        range_add(1, entry[chain_top[u]], entry[u], delta);
        u = parent[chain_top[u]];
    }
    if (depth[u] > depth[v]) std::swap(u, v);
    range_add(1, entry[u], entry[v], delta);
}

int query_path(int u, int v) {
    int res = 0;
    while (chain_top[u] != chain_top[v]) {
        if (depth[chain_top[u]] < depth[chain_top[v]]) std::swap(u, v);
        res = (res + range_sum(1, entry[chain_top[u]], entry[u])) % MOD_VAL;
        u = parent[chain_top[u]];
    }
    if (depth[u] > depth[v]) std::swap(u, v);
    res = (res + range_sum(1, entry[u], entry[v])) % MOD_VAL;
    return res;
}

Subtree operations rely directly on the previously established continuous property:

void modify_subtree(int u, int delta) {
    range_add(1, entry[u], entry[u] + size[u] - 1, delta);
}

int query_subtree(int u) {
    return range_sum(1, entry[u], entry[u] + size[u] - 1);
}

Complete implementation integrating the segment tree:

#include <iostream>
#include <vector>

using namespace std;
const int MAXN = 100005;

int N, M, root, MOD_VAL;
int values[MAXN];
vector<int> adj[MAXN];

struct SegmentNode {
    int l, r, sum_val, lazy_tag;
} seg[MAXN << 2];

int left_child(int i) { return i << 1; }
int right_child(int i) { return i << 1 | 1; }

void push_up(int i) {
    seg[i].sum_val = (seg[left_child(i)].sum_val + seg[right_child(i)].sum_val) % MOD_VAL;
}

void push_down(int i) {
    if (seg[i].lazy_tag) {
        int lt = seg[i].lazy_tag;
        SegmentNode &lc = seg[left_child(i)], &rc = seg[right_child(i)];
        
        lc.lazy_tag = (lc.lazy_tag + lt) % MOD_VAL;
        lc.sum_val = (lc.sum_val + lt * (lc.r - lc.l + 1)) % MOD_VAL;
        
        rc.lazy_tag = (rc.lazy_tag + lt) % MOD_VAL;
        rc.sum_val = (rc.sum_val + lt * (rc.r - rc.l + 1)) % MOD_VAL;
        
        seg[i].lazy_tag = 0;
    }
}

void construct_tree(int i, int l, int r) {
    seg[i].l = l; seg[i].r = r;
    seg[i].sum_val = 0; seg[i].lazy_tag = 0;
    if (l == r) return;
    int mid = (l + r) >> 1;
    construct_tree(left_child(i), l, mid);
    construct_tree(right_child(i), mid + 1, r);
}

void range_add(int i, int ql, int qr, int delta) {
    if (ql <= seg[i].l && seg[i].r <= qr) {
        seg[i].sum_val = (seg[i].sum_val + delta * (seg[i].r - seg[i].l + 1)) % MOD_VAL;
        seg[i].lazy_tag = (seg[i].lazy_tag + delta) % MOD_VAL;
        return;
    }
    push_down(i);
    int mid = (seg[i].l + seg[i].r) >> 1;
    if (ql <= mid) range_add(left_child(i), ql, qr, delta);
    if (qr > mid) range_add(right_child(i), ql, qr, delta);
    push_up(i);
}

int range_sum(int i, int ql, int qr) {
    if (ql <= seg[i].l && seg[i].r <= qr) return seg[i].sum_val;
    push_down(i);
    int mid = (seg[i].l + seg[i].r) >> 1;
    int ans = 0;
    if (ql <= mid) ans = (ans + range_sum(left_child(i), ql, qr)) % MOD_VAL;
    if (qr > mid) ans = (ans + range_sum(right_child(i), ql, qr)) % MOD_VAL;
    return ans;
}

int size[MAXN], parent[MAXN], depth[MAXN], heavy[MAXN];
int chain_top[MAXN], entry[MAXN], cur_pos = 0;

void first_dfs(int u, int p) {
    size[u] = 1;
    parent[u] = p;
    depth[u] = depth[p] + 1;
    heavy[u] = -1;
    int max_sz = 0;
    for (int v : adj[u]) {
        if (v != p) {
            first_dfs(v, u);
            size[u] += size[v];
            if (size[v] > max_sz) {
                max_sz = size[v];
                heavy[u] = v;
            }
        }
    }
}

void second_dfs(int u, int p, int top_node) {
    chain_top[u] = top_node;
    entry[u] = ++cur_pos;
    if (heavy[u] != -1) {
        second_dfs(heavy[u], u, top_node);
    }
    for (int v : adj[u]) {
        if (v != p && v != heavy[u]) {
            second_dfs(v, u, v);
        }
    }
}

void modify_path(int u, int v, int delta) {
    while (chain_top[u] != chain_top[v]) {
        if (depth[chain_top[u]] < depth[chain_top[v]]) swap(u, v);
        range_add(1, entry[chain_top[u]], entry[u], delta);
        u = parent[chain_top[u]];
    }
    if (depth[u] > depth[v]) swap(u, v);
    range_add(1, entry[u], entry[v], delta);
}

int query_path(int u, int v) {
    int res = 0;
    while (chain_top[u] != chain_top[v]) {
        if (depth[chain_top[u]] < depth[chain_top[v]]) swap(u, v);
        res = (res + range_sum(1, entry[chain_top[u]], entry[u])) % MOD_VAL;
        u = parent[chain_top[u]];
    }
    if (depth[u] > depth[v]) swap(u, v);
    res = (res + range_sum(1, entry[u], entry[v])) % MOD_VAL;
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> N >> M >> root >> MOD_VAL;
    for (int i = 1; i <= N; ++i) cin >> values[i];
    
    for (int i = 1; i < N; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    first_dfs(root, 0);
    second_dfs(root, 0, root);
    construct_tree(1, 1, N);
    
    for (int i = 1; i <= N; ++i) {
        range_add(1, entry[i], entry[i], values[i]);
    }
    
    while (M--) {
        int op;
        cin >> op;
        if (op == 1) {
            int u, v, z;
            cin >> u >> v >> z;
            modify_path(u, v, z);
        } else if (op == 2) {
            int u, v;
            cin >> u >> v;
            cout << query_path(u, v) << "\n";
        } else if (op == 3) {
            int u, z;
            cin >> u >> z;
            range_add(1, entry[u], entry[u] + size[u] - 1, z);
        } else if (op == 4) {
            int u;
            cin >> u;
            cout << range_sum(1, entry[u], entry[u] + size[u] - 1) << "\n";
        }
    }
    return 0;
}

Heavy-Light Decomposition provides an efficient O(log N) method to find the Lowest Common Ancestor (LCA) without the space overhead of binary lifting. By ascending the chains until both nodes share the same chain top, the shallower node acts as the LCA.

int get_lca(int u, int v) {
    while (chain_top[u] != chain_top[v]) {
        if (depth[chain_top[u]] < depth[chain_top[v]]) swap(u, v);
        u = parent[chain_top[u]];
    }
    return depth[u] < depth[v] ? u : v;
}