Tree Algorithm

Lowest Common Ancestor

https://contest.yandex.com/contest/70295/problems/E/
- $O (n lo g C)$ 次詢問某個樹的點集 subset 上離某個點最遠的點距離

支援操作：

void init(int n)
- 初始化點集合為 $[0, n]$ ，代表 $0$ -base 或 $1$ -base 皆可
void add_edge(int u, int v)
- 加無向不帶權的邊 $(u, v)$
void build()
- $⟨ O (n lo g n), O (n lo g n)⟩$ DFS + 建 Sparse Table
int lca(int u, int v)
- $O (1)$ 找 $u$ 與 $v$ 的最近共同祖先
int lca_jump(int u, int v)
- $O (lo g n)$ 找 $u$ 與 $v$ 的最近共同祖先，需要把 anc[][] 相關的註解拿掉
int jump(int u, int k) untested
- $O (lo g n)$ 找 $u$ 往上第 $k$ 個祖先，需要把 anc[][] 相關的註解拿掉
int dist(int u, int v)
- $O (1)$ 找 $u$ 與 $v$ 的距離

支援不連通的森林，但在做 LCA 時，請確保 $u$ 與 $v$ 連通

Code

struct LCA {
    
    vector<vector<int>> adj;
    // vector<vector<int>> anc;
    vector<vector<int>> sp_table;
    vector<int> dep, dfn_i, dfn_o;
    int lgmx, maxn;
    
    void init(int N) {
        maxn = N + 1;
        lgmx = __lg(maxn) + 2;
        adj.resize(maxn);
        // anc.assign(lgmx, vector<int>(maxn, -1));
        sp_table.assign(lgmx, vector<int>(2*maxn, 0));
        dep.assign(maxn, 0);
        dfn_i.assign(maxn, -1);
        dfn_o.assign(maxn, -1);
    }
    
    void add_edge(int u, int v) {
        adj[u].eb(v), adj[v].eb(u);
    }
    
    void build() {
        int tok_dfn = 0;
        function<void(int, int)> dfs = [&](int now, int lst) {
            // anc[0][now] = lst;
            dfn_i[now] = dfn_o[now] = tok_dfn;
            sp_table[0][tok_dfn++] = now;
            for (int x : adj[now]) {
                if (x == lst) continue;
                dep[x] = dep[now] + 1, dfs(x, now);
                dfn_o[now] = tok_dfn;
                sp_table[0][tok_dfn++] = now;
            }
        };
        for (int i = 0; i < maxn; ++i) { if (dfn_i[i] == -1) dfs(i, i); }
        // for (int lay = 1; lay < lgmx; ++lay) {
        //     for (int i = 0; i < maxn; ++i) anc[lay][i] = anc[lay-1][anc[lay-1][i]];
        // }
        for (int lay = 1; lay < lgmx; ++lay) {
            for (int i = 0, j = 1<<(lay-1); i < 2*maxn; ++i, ++j) {
                if (j >= 2*maxn) { sp_table[lay][i] = sp_table[lay-1][i]; continue; }
                int L = sp_table[lay-1][i], R = sp_table[lay-1][j];
                sp_table[lay][i] = (dfn_i[L] < dfn_i[R] ? L : R);
            }
        }
        
        // debug(dep);
        // debug(dfn_i);
        // debug(dfn_o);
    }
    
    int lca(int u, int v) {
        tie(u, v) = pii(min(dfn_i[u], dfn_i[v]), max(dfn_o[u], dfn_o[v]));
        int lay = __lg(v - u + 1);
        int L = sp_table[lay][u], R = sp_table[lay][v-(1<<lay)+1];
        return (dfn_i[L] < dfn_i[R] ? L : R);
    }
    
    // int lca_jump(int u, int v) {
    //     if (dep[u] < dep[v]) swap(u, v);
    //     for (int lay = lgmx-1, dif = dep[u] - dep[v]; lay >= 0; --lay) {
    //         if (dif >> lay & 1) u = anc[lay][u];
    //     }
    //     if (u == v) return u;
    //     for (int lay = lgmx-1; lay >= 0; --lay) {
    //         if (anc[lay][u] != anc[lay][v]) u = anc[lay][u], v = anc[lay][v];
    //     }
    //     return anc[0][u];
    // }
    
    // int jump(int u, int k) {
    //     for (int lay = lgmx-1; lay >= 0; --lay) {
    //         if (k >> lay & 1) u = anc[lay][u];
    //     }
    //     return u;
    // }
    
    int dist(int u, int v) {
        int c = lca(u, v);
        // assert(c == lca_jump(u, v));
        return dep[u] + dep[v] - 2 * dep[c];
    }
    
};

Lowest Common Ancestor with Information on Edges

支援操作（基本同上）：

void init(int n)
- 初始化點集合為 $[0, n]$ ，代表 $0$ -base 或 $1$ -base 皆可
void add_edge(int u, int v, const Info &info)
- 加無向不帶權的邊 $(u, v)$ ，邊上帶有資訊 info
void build()
- $⟨ O (n lo g n), O (n lo g n)⟩$ DFS + 建跳表
pair<int, Info> lca_jump(int u, int v)
- $O (lo g n)$ 找 $u$ 與 $v$ 的最近共同祖先
Info get_info(int u, int v)
- $O (lo g n)$ 回傳 $u$ 與 $v$ 之間的邊上的資訊（只是 call 了一次 lca_jump）
int jump(int u, int k) untested
- $O (lo g n)$ 找 $u$ 往上第 $k$ 個祖先
int dist(int u, int v)
- $O (1)$ 找 $u$ 與 $v$ 的距離

需要自定義 struct Info，並實作

Info() (default constructor)
Info& operator += (const Info &rhs)
friend Info operator + (Info lhs, const Info &rhs)

此處的資訊是無向的，必須滿足交換律才能使用，否則還需稍作修改

Code

template <typename Info>
struct LCA {
    
    vector<vector<pair<int, Info>>> adj;
    vector<vector<pair<int, Info>>> anc;
    vector<int> dep, vis;
    int lgmx, maxn;
    
    void init(int N) {
        maxn = N + 1;
        lgmx = __lg(maxn) + 2;
        adj.resize(maxn);
        anc.assign(lgmx, vector(maxn, make_pair(int(0), Info())));
        dep.assign(maxn, 0);
        vis.assign(maxn, 0);
    }
    
    void add_edge(int u, int v, const Info &info) {
        adj[u].eb(v, info), adj[v].eb(u, info);
    }
    
    void build() {
        function<void(int, int)> dfs = [&](int now, int lst) {
            vis[now] = 1;
            for (auto [x, info] : adj[now]) {
                if (x == lst) continue;
                dep[x] = dep[now] + 1, dfs(x, now);
                anc[0][x] = {now, info};
            }
        };
        for (int i = 0; i < maxn; ++i) { if (vis[i] == 0) dfs(i, i); }
        
        for (int lay = 1; lay < lgmx; ++lay) {
            for (int i = 0; i < maxn; ++i) {
                int p = anc[lay-1][i].first;
                anc[lay][i].first = anc[lay-1][p].first;
                anc[lay][i].second = anc[lay-1][i].second + anc[lay-1][p].second;
            }
        }
        
        // debug(dep);
    }
    
    pair<int, Info> lca_jump(int u, int v) {
        if (dep[u] < dep[v]) swap(u, v);
        Info ans;
        for (int lay = lgmx-1, dif = dep[u] - dep[v]; lay >= 0; --lay) {
            if (dif >> lay & 1) ans += anc[lay][u].second, u = anc[lay][u].first;
        }
        if (u == v) return {u, ans};
        for (int lay = lgmx-1; lay >= 0; --lay) {
            if (anc[lay][u].first != anc[lay][v].first) {
                ans += anc[lay][u].second, u = anc[lay][u].first;
                ans += anc[lay][v].second, v = anc[lay][v].first;
            }
        }
        ans += anc[0][u].second, u = anc[0][u].first;
        ans += anc[0][v].second, v = anc[0][v].first;
        return {u, ans};
    }
    
    Info get_info(int u, int v) {
        return lca_jump(u, v).second;
    }
    
    int jump(int u, int k) {
        for (int lay = lgmx-1; lay >= 0; --lay) {
            if (k >> lay & 1) u = anc[lay][u].first;
        }
        return u;
    }
    
    int dist(int u, int v) {
        auto [c, info] = lca_jump(u, v);
        return dep[u] + dep[v] - 2 * dep[c];
    }
    
};

struct Info {
    
    int val;
    
    Info() : val(INT_MAX) {}
    Info(int _val) : val(_val) {}
    
    Info& operator += (const Info &rhs) {
        val = min(val, rhs.val);
        return *this;
    }
    
    friend Info operator + (Info lhs, const Info &rhs) {
        lhs.val = min(lhs.val, rhs.val);
        return lhs;
    }
    
};

SorahISA's Contest Logs

Tree Algorithm

Lowest Common Ancestor

Lowest Common Ancestor with Information on Edges