Algoogle

Algorithm for Programming Contest

基本情報


計算量(構築)
計算量(LCA)

V := 頂点数

解説


コード


(tree.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
using graph = vector<vector<int>>;
class tree {
    graph G;
    int root, V, logV;
    vector<vector<int>> par;
    vector<int> dep;

    void dfs(int v, int u) {
        if(~u) {
            dep[v] = dep[u]+1;
            par[v][0] = u;
            int k = 0;
            while(par[par[v][k]][k] >= 0) {
                par[v][k+1] = par[par[v][k]][k];
                k++;
            }
        }
        for(int &w: G[v]) if(w != u) dfs(w,v);
    }

public:
    tree() {}
    tree(const graph &G, int root = 0) : G(G), root(root) {
        V = G.size();
        logV = 1;
        while((1<<logV) < V) logV++;
        dep.assign(V,0);
        par.assign(V,vector<int>(logV,-1));
        dfs(root,-1);
    }

    int lca(int u, int v) {
        if(dep[u] > dep[v]) swap(u,v);
        int diff = dep[v]-dep[u];
        for(int i = 0; i < logV; i++)
            if(diff&(1<<i)) v = par[v][i];
        if(u == v) return u;
        for(int i = logV-1; i >= 0; i--)
            if(par[u][i] != par[v][i]) {
                u = par[u][i];
                v = par[v][i];
            }
        return par[u][0];
    }

    int dist(int u, int v) { return dep[u]+dep[v]-2*dep[lca(u,v)]; }
};

Comments