Submission #230694

---

Source Code Expand

#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
using namespace std;

class LowestCommonAncestor
{
private:
    vector<vector<int> > to;
    vector<int> depth;
    void dfs(const vector<vector<int> >& edges, int curr, int prev, int cnt)
    {
        depth[curr] = cnt;
        if(prev != -1){
            to[curr].push_back(prev);
            int j = prev;
            unsigned k = 0;
            while(k < to[j].size()){
                j = to[j][k];
                to[curr].push_back(j);
                ++ k;
            }
        }
        for(unsigned i=0; i<edges[curr].size(); ++i){
            int next = edges[curr][i];
            if(next != prev)
                dfs(edges, next, curr, cnt + 1);
        }
    }
    int climb(int curr, int dist)
    {
        int i = 0;
        while(dist > 0){
            if(dist % 2 == 1)
                curr = to[curr][i];
            dist /= 2;
            ++ i;
        }
        return curr;
    }
public:
    LowestCommonAncestor(const vector<vector<int> >& edges, int root)
    {
        int n = edges.size();
        to.assign(n, vector<int>());
        depth.resize(n);
        dfs(edges, root, -1, 0);
    }
    int query(int a, int b)
    {
        pair<int, int> dist(0, 0);
        int diff = depth[a] - depth[b];
        if(diff < 0){
            b = climb(b, -diff);
            dist.second += -diff;
        }
        else{
            a = climb(a, diff);
            dist.first += diff;
        }

        if(a == b)
            return dist.first + dist.second;

        int x = to[a].size() - 1;
        while(x >= 0){
            int y = x / 2;
            if(to[a][y] == to[b][y]){
                x = y - 1;
            }
            else{
                a = to[a][y];
                b = to[b][y];
                dist.first += 1 << y;
                dist.second += 1 << y;
                -- x;
            }
        }

        return dist.first + dist.second + 2;
    }
};

int main()
{
    int n;
    cin >> n;
    vector<vector<int> > edges(n);
    for(int i=0; i<n-1; ++i){
        int x, y;
        cin >> x >> y;
        edges[x-1].push_back(y-1);
        edges[y-1].push_back(x-1);
    }
    LowestCommonAncestor lca(edges, 0);

    int q;
    cin >> q;
    while(--q >= 0){
        int a, b;
        cin >> a >> b;
        cout << (lca.query(a-1, b-1) + 1) << endl;
    }

    return 0;
}

Submission Info

Judge Result