Heavy-light-декомпозиция

#include <stdio.h>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <iostream>
using namespace std;

class ST {
    int *t, size;
    void build(int v, int vl, int vr) {
        if (vl == vr) {
            t[v] = 0;
            return;
        }
        int vm = vl + (vr - vl) / 2;
        build(2 * v + 1, vl, vm);
        build(2 * v + 2, vm + 1, vr);
        t[v] = max(t[2 * v + 1], t[2 * v + 2]);
    }
    int query(int v, int vl, int vr, int l, int r) {
        if (r < vl || vr < l)
            return -(1 << 30);
        if (l <= vl && vr <= r)
            return t[v];
        int vm = vl + (vr - vl) / 2;
        int ql = query(2 * v + 1, vl, vm, l, r);
        int qr = query(2 * v + 2, vm + 1, vr, l, r);
        return max(ql, qr);
    }
    void modify(int v, int vl, int vr, int pos, int val) {
        if (pos < vl || vr < pos)
            return;
        if (pos == vl && vl == vr) {
            t[v] += val;
            return;
        }
        int vm = vl + (vr - vl) / 2;
        modify(2 * v + 1, vl, vm, pos, val);
        modify(2 * v + 2, vm + 1, vr, pos, val);
        t[v] = max(t[2 * v + 1], t[2 * v + 2]);
    }
public:
    ST() {}
    ST(int n) {
        t = new int[4 * n];
        size = n;
        build(0, 0, size - 1);
    }
    int query(int l, int r) {
        return query(0, 0, size - 1, l, r);
    }
    void modify(int pos, int val) {
        modify(0, 0, size - 1, pos, val);
    }
} st[100010];

int n, q, a, b;
char c;
vector<int> g[100010];
int tIn[100010], tOut[100010], timer, size[100010], parent[100010];

void dfs(int v) {
    tIn[v] = ++timer;
    size[v] = 1;
    for (int i = 0; i < g[v].size(); i++) {
        if (!tIn[g[v][i]]) {
            parent[g[v][i]] = v;
            dfs(g[v][i]);
            size[v] += size[g[v][i]];
        }
    }
    tOut[v] = ++timer;
}

bool isAncestor(int a, int v) {
    return tIn[a] <= tIn[v] && tOut[v] <= tOut[a];
}

int chainInd[100010], chainPos[100010];
int chainSize[100010], chainRoot[100010];
int chainsCount;

void buildHLD(int v, int chain) {
    chainInd[v] = chain;
    chainPos[v] = chainSize[chain];
    chainSize[chain]++;
    if (chainSize[chain] == 1)
        chainRoot[chain] = v;
    int maxChild = -1;
    for (int i = 0; i < g[v].size(); i++) {
        if (g[v][i] != parent[v] && (maxChild == -1 || size[g[v][i]] > size[g[v][maxChild]]))
            maxChild = i;
    }
    if (maxChild != -1)
        
    for (int i = 0; i < g[v].size(); i++) {
        if (g[v][i] == parent[v])
            continue;
        if (i == maxChild)
            buildHLD(g[v][i], chain);
        else
            buildHLD(g[v][i], chainsCount++);
    }
}

int queryHLD(int a, int b) {
    int res = 0;
    while (1) {
        if (isAncestor(chainRoot[chainInd[a]], b))
            break;
        res = max(res, st[chainInd[a]].query(0, chainPos[a]));
        a = parent[chainRoot[chainInd[a]]];
    }
    while (1) {
        if (isAncestor(chainRoot[chainInd[b]], a))
            break;
        res = max(res, st[chainInd[b]].query(0, chainPos[b]));
        b = parent[chainRoot[chainInd[b]]];
    }
    if (chainPos[a] > chainPos[b])
        swap(a, b);
    return max(res, st[chainInd[a]].query(chainPos[a], chainPos[b]));
}

int main() {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

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

    dfs(0);
    buildHLD(0, chainsCount++);
    for (int i = 0; i < chainsCount; i++)
        st[i] = ST(chainSize[i]);

    scanf("%d", &q);
    for (int i = 0; i < q; i++) {
        scanf(" %c%d%d", &c, &a, &b);
        if (c == 'I')
            st[chainInd[a - 1]].modify(chainPos[a - 1], b);
        else
            printf("%d\n", queryHLD(a - 1, b - 1));
    }
}

Ссылки на задачи

• Timus #1553 — Caves and Tunnels

Ссылки

• e-maxx.ru — Heavy-light декомпозиция
• blog.anudeep2011.com — Heavy Light Decomposition
• CodeLibrary — Heavy-light tree decomposition for edges or vertices
• Algos — Heavy-light decomposition with segment trees in paths
• Algos — Finding LCA (Least common ancestor) of two vertices in the tree. Uses heavy-light decomposition