Submission #1473302

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
using llng = long long;
template<typename T> using v = vector<T>;
template<typename T> using vv = v<v<T> >;

class Graph {
    int N;
    void add_edge(int v1, int v2, int cap, bool isUndirected) {
        int v1_rev = edge[v2].size(), v2_rev = edge[v1].size();
        edge[v1].push_back(Edge(v2, cap, v1_rev));
        edge[v2].push_back(Edge(v1, (isUndirected ? cap : 0), v2_rev));
    }
public:
    struct Edge {
        int to, cap, rev;
        Edge(int _t, int _c, int _r) : to(_t), cap(_c), rev(_r) {}
    };
    vector<vector<Edge> > edge;
    Graph() {}
    Graph(int _N) : N(_N) { edge = vector<vector<Edge> >(N); }
    void add(int v1, int v2, int cap = 1) { add_edge(v1, v2, cap, true); }
    void add_d(int from, int to, int cap = 1) { add_edge(from, to, cap, false); }
    int size() const { return N; }
};

template<typename T> class SegTree {
    void eval(int v) { seg[v] = eval(seg[v*2], seg[v*2+1]); }
    T query(int a, int b, int v, int l, int r) {
        if (r <= a || b <= l) return error();
        if (a <= l && r <= b) return seg[v];
        T vl = query(a, b, v*2, l, (l+r)/2);
        T vr = query(a, b, v*2+1, (l+r)/2, r);
        return eval(vl, vr);
    }
protected:
    int n;
    vector<T> seg;
    virtual T error() = 0;
    virtual T eval(T t1, T t2) = 0;
public:
    SegTree() {}
    SegTree(vector<T> vec) : n(vec.size()) {
        n--; for (int i=1; i<32; i<<=1) n |= (n >> i); n++;
        seg = vector<T>(n); seg.insert(seg.end(), vec.begin(), vec.end());
    }
    void build() { for (int i=n-1; i>0; i--) eval(i); }
    virtual void update(int i, T t) final {
        i += n; seg[i] = t;
        while (i > 0) { i >>= 1; eval(i); }
    }
    virtual T query(int a, int b) final { return query(a, b, 1, 0, n); }
};

class EulerTour {
    const Graph g;
    vector<int> et_node, et_depth, et_id;
    void et_update(int v, int d) {
        et_node.push_back(v);
        et_depth.push_back(d);
    }
    void euler_tour(int v, int p, int d) {
        et_id[v] = et_node.size();
        et_update(v, d);
        for (auto e : g.edge[v]) if (e.to != p) {
            euler_tour(e.to, v, d+1);
            et_update(v, d);
        }
    }
public:
    EulerTour() {}
    EulerTour(const Graph _g, int s) : g(_g) {
        et_node = et_depth = vector<int>(0);
        et_id = vector<int>(g.size());
        euler_tour(s, -1, 0);
    }
    const vector<int> &node() const { return et_node; }
    const vector<int> &depth() const { return et_depth; }
    const vector<int> &id() const { return et_id; }
    int node(int v) const { return et_node[et_id[v]]; }
    int depth(int v) const { return et_depth[et_id[v]]; }
};

class LCA {
    class LCARMQ : public SegTree<pair<int, int> > {
    protected:
        pair<int, int> error() { return make_pair(1e9, -1); }
        pair<int, int> eval(pair<int, int> t1, pair<int, int> t2) {
            return min(t1, t2);
        }
    public:
        using SegTree::SegTree;
    } seg;
    const EulerTour et;
    int lca_id(int a, int b) {
        int l = min(et.id()[a], et.id()[b]);
        int r = max(et.id()[a], et.id()[b]);
        return seg.query(l, r+1).second;
    }
public:
    LCA(const EulerTour _et) : et(_et) {
        vector<pair<int, int> > idx;
        for (int i=0; i<et.depth().size(); i++) {
            idx.push_back(make_pair(et.depth()[i], i));
        }
        seg = LCARMQ(idx); seg.build();
    }
    int node(int a, int b) { return et.node()[lca_id(a, b)]; }
    int depth(int a, int b) { return et.depth()[lca_id(a, b)]; }
};

int main() {
    int a, b, N; cin >> N;
    Graph g(N+1);
    for (int i=0; i<N-1; i++) { cin >> a >> b; g.add(a, b, 1); }
    EulerTour et(g, 1); LCA lca(et);
    int Q; cin >> Q;
    for (int i=0; i<Q; i++) {
        cin >> a >> b;
        cout << et.depth(a) + et.depth(b) - 2*lca.depth(a, b) + 1 << endl;
    }
    return 0;
}

Submission Info

Judge Result