Solution of cf 121, div2, E using LCA in logN

cf_121_d2_e.cpp

// Solution for http://codeforces.com/contest/192/problem/E
// You are given a tree and in each node of the tree there is a person (called full further)
// which goes to another person living in different node.
// You need to compute for every edge how many persons will pass through it.
// We decompose the path from one person to another using LCA.
// Using LCA algorithm which requires logN operations for search

#include <bits/stdc++.h>
using namespace std;
typedef long long int lint;
typedef long double ldouble;

int n;
vector< vector<int> > adj;

// save time when we get into vertex and leave it
// it allows to check ancestor/child relationships
const int NM = 1e5 + 1;
int timer;
int tin[NM], tout[NM];
int parent[NM][22]; // structure to speed up lca search to logN
// parent[v][0] - just parent (1st ancestor)
// parent[v][i] - 2^i ancestor of v

// cur is current vertex, p - parent
// since it is tree it is enough to have parent to avoid
// visiting the same vertex twice
void dfs(int cur, int p) {
    tin[cur] = timer++;
    
    // fill in parents using dynamical programming
    parent[cur][0] = p;
    for (int i = 1; i < 22; ++i) {
        int v = parent[cur][i-1];
        if (v != -1) {
            parent[cur][i] = parent[v][i-1];
        } else {
            parent[cur][i] = -1;
        }
    }

    for (int u : adj[cur]) {
        if (u != p) {
            dfs(u, cur);
        }
    }

    tout[cur] = timer++;
}

// check if ancestor
bool isAnc(int child, int p) {
    if (p == -1) // above root
        return true;
    if (tin[child] >= tin[p] && tout[child] <= tout[p])
        return true;
    return false;
}

// least common ancestor in log(N)
int lca(int u, int v) {
    if (isAnc(u,v))
        return v;
    if (isAnc(v, u))
        return u;

    for (int i = 21; i >= 0; --i) {
        int p = parent[u][i];
        if (!isAnc(v, p)) {
            u = p;
        }    
    } 
    // top but not parent
    return parent[u][0];
}

int start[NM];
int finish[NM];
void propagate(int cur, int p) {
    for (int u : adj[cur])
        if (u != p) {
            propagate(u, cur);
            start[cur] += start[u];
            finish[cur] += finish[u];
        }
}

int main(int, char**) {
    std::ios::sync_with_stdio(false);

    //1. read the graph
    cin >> n;
    adj.resize(n);
    vector< pair<int, int> > edges(n-1);
    for (int i = 0; i < n-1; ++i) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        edges[i] = {u, v};
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    // 2. Build oriented tree made up by dfs
    dfs(0, -1);

    // 3. read pairs of fulls and
    // split path a->b into two: a->lca(a,b), b->lca(a,b)
    // save information about number of pathes starting at vertex and number of ending there
    int k;
    cin >> k;
    for (int i = 0; i < k; ++i) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        int curLca = lca(u, v);
        if (curLca == u) {
            ++finish[curLca];
            ++start[v];
        } else if (curLca == v) {
            ++finish[curLca];
            ++start[u];
        } else { // split path into two as discussed
            finish[curLca] += 2;
            ++start[u];
            ++start[v];
        }
    }

    // 4. Propagate information about number of path having start/finish at current vertex
    propagate(0, -1);
    for (auto e : edges) {
        // take vertex which is below in the tree
        int v = e.first;
        if (tin[v] < tin[e.second])
            v = e.second;
        cout << start[v] - finish[v]  << endl;
    } 

    return 0;
}