Library

This documentation is automatically generated by competitive-verifier/competitive-verifier

View the Project on GitHub anmichi/Library

:heavy_check_mark: AuxiliaryTree.cpp

Depends on

Verified with

Code

#include <bits/stdc++.h>
#include "LCA.cpp"
using namespace std;
struct auxiliary_tree : lca_tree {
    vector<vector<int>> G;
    auxiliary_tree(vector<vector<int>>& g) : lca_tree(g), G(n) {}
    pair<int, vector<int>> query(vector<int> vs, bool decending = false) {
        // decending:親から子の方向のみ辺を貼る
        assert(!vs.empty());
        sort(vs.begin(), vs.end(), [&](int a, int b) { return in[a] < in[b]; });
        int m = vs.size();
        stack<int> st;
        st.push(vs[0]);
        for (int i = 0; i < m - 1; i++) {
            int w = lca(vs[i], vs[i + 1]);
            if (w != vs[i]) {
                int l = st.top();
                st.pop();
                while (!st.empty() && depth[w] < depth[st.top()]) {
                    if (!decending) G[l].push_back(st.top());
                    G[st.top()].push_back(l);
                    l = st.top();
                    st.pop();
                }
                if (st.empty() || st.top() != w) {
                    st.push(w);
                    vs.push_back(w);
                }
                if (!decending) G[l].push_back(w);
                G[w].push_back(l);
            }
            st.push(vs[i + 1]);
        }
        while (st.size() > 1) {
            int x = st.top();
            st.pop();
            if (!decending) G[x].push_back(st.top());
            G[st.top()].push_back(x);
        }
        // {root,vertex_list}
        return make_pair(st.top(), vs);
    }
    void clear(vector<int> vs) {
        for (int v : vs) G[v].clear();
    }
};
#line 1 "AuxiliaryTree.cpp"
#include <bits/stdc++.h>
#line 2 "SparseTable.cpp"
using namespace std;
template <class T, T (*op)(T, T), T (*e)()>
struct sparsetable {
    vector<vector<T>> table;
    vector<int> logtable;
    sparsetable() = default;
    sparsetable(vector<T> v) {
        int len = 0;
        while ((1 << len) <= (int)v.size()) len++;
        table.assign(len, vector<T>(1 << len));
        for (int i = 0; i < (int)v.size(); i++) table[0][i] = v[i];
        for (int i = 1; i < len; i++) {
            for (int j = 0; j + (1 << i) <= (1 << len); j++) {
                table[i][j] = op(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);
            }
        }
        logtable.resize((int)v.size() + 1);
        for (int i = 2; i < (int)logtable.size(); i++) {
            logtable[i] = logtable[(i >> 1)] + 1;
        }
    }
    T query(int l, int r) {
        assert(l <= r);
        if (l == r) return e();
        int len = logtable[r - l];
        return op(table[len][l], table[len][r - (1 << len)]);
    }
};
template <class T, T (*op)(T, T), T (*e)()>
struct disjointsparsetable {
    vector<vector<T>> table;
    vector<int> logtable;
    disjointsparsetable() = default;
    disjointsparsetable(vector<T> v) {
        int len = 0;
        while ((1 << len) <= v.size()) len++;
        table.assign(len, vector<T>(1 << len, e()));
        for (int i = 0; i < (int)v.size(); i++) table[0][i] = v[i];
        for (int i = 1; i < len; i++) {
            int shift = 1 << i;
            for (int j = 0; j < (int)v.size(); j += shift << 1) {
                int t = min(j + shift, (int)v.size());
                table[i][t - 1] = v[t - 1];
                for (int k = t - 2; k >= j; k--) table[i][k] = op(v[k], table[i][k + 1]);
                if (v.size() <= t) break;
                table[i][t] = v[t];
                int r = min(t + shift, (int)v.size());
                for (int k = t + 1; k < r; k++) table[i][k] = op(table[i][k - 1], v[k]);
            }
        }
        logtable.resize(1 << len);
        for (int i = 2; i < logtable.size(); i++) {
            logtable[i] = logtable[(i >> 1)] + 1;
        }
    }
    T query(int l, int r) {
        if (l == r) return e();
        if (l >= --r) return table[0][l];
        int len = logtable[l ^ r];
        return op(table[len][l], table[len][r]);
    };
};
#line 3 "LCA.cpp"
using namespace std;
pair<int, int> lcatree_op(pair<int, int> a, pair<int, int> b) { return min(a, b); }
pair<int, int> lcatree_e() { return {1000000000, -1}; }
struct lca_tree {
    int n, size;
    vector<int> in, ord, depth;
    disjointsparsetable<pair<int, int>, lcatree_op, lcatree_e> st;
    lca_tree(vector<vector<int>> g, int root = 0) : n((int)g.size()), size(log2(n) + 2), in(n), depth(n, n) {
        depth[root] = 0;
        function<void(int, int)> dfs = [&](int v, int p) {
            in[v] = (int)ord.size();
            ord.push_back(v);
            for (int u : g[v]) {
                if (u == p) continue;
                if (depth[u] > depth[v] + 1) {
                    depth[u] = depth[v] + 1;
                    dfs(u, v);
                    ord.push_back(v);
                }
            }
        };
        dfs(root, -1);
        vector<pair<int, int>> vec((int)ord.size());
        for (int i = 0; i < (int)ord.size(); i++) {
            vec[i] = make_pair(depth[ord[i]], ord[i]);
        }
        st = vec;
    }
    int lca(int u, int v) {
        if (in[u] > in[v]) swap(u, v);
        if (u == v) return u;
        return st.query(in[u], in[v]).second;
    }
    int dist(int u, int v) {
        int l = lca(u, v);
        return depth[u] + depth[v] - 2 * depth[l];
    }
};
#line 3 "AuxiliaryTree.cpp"
using namespace std;
struct auxiliary_tree : lca_tree {
    vector<vector<int>> G;
    auxiliary_tree(vector<vector<int>>& g) : lca_tree(g), G(n) {}
    pair<int, vector<int>> query(vector<int> vs, bool decending = false) {
        // decending:親から子の方向のみ辺を貼る
        assert(!vs.empty());
        sort(vs.begin(), vs.end(), [&](int a, int b) { return in[a] < in[b]; });
        int m = vs.size();
        stack<int> st;
        st.push(vs[0]);
        for (int i = 0; i < m - 1; i++) {
            int w = lca(vs[i], vs[i + 1]);
            if (w != vs[i]) {
                int l = st.top();
                st.pop();
                while (!st.empty() && depth[w] < depth[st.top()]) {
                    if (!decending) G[l].push_back(st.top());
                    G[st.top()].push_back(l);
                    l = st.top();
                    st.pop();
                }
                if (st.empty() || st.top() != w) {
                    st.push(w);
                    vs.push_back(w);
                }
                if (!decending) G[l].push_back(w);
                G[w].push_back(l);
            }
            st.push(vs[i + 1]);
        }
        while (st.size() > 1) {
            int x = st.top();
            st.pop();
            if (!decending) G[x].push_back(st.top());
            G[st.top()].push_back(x);
        }
        // {root,vertex_list}
        return make_pair(st.top(), vs);
    }
    void clear(vector<int> vs) {
        for (int v : vs) G[v].clear();
    }
};
Back to top page