Heavy Light Decomposition.

Solution for Live Archive 2045 - Closest Common Ancestors

/*
 * 11354.cpp
 *
 *  Created on: Sep 1, 2014
 *      Author: ghooo
 */

#include <cstring>
#include <map>
#include <deque>
#include <queue>
#include <stack>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <vector>
#include <set>
#include <complex>
#include <list>
#include <climits>
#include <cctype>
#include <bitset>
//#include <windows.h>

using namespace std;

#define pb push_back
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define sz(v) ((ll)v.size())
#define rep(i,m) for(int i=0;i<(int)(m);++i)
#define repe(i,n,m) for(int i=n;i<=(int)(m);++i)
#define rep2(i,n,m) for(int i=n;i<(int)(m);i++)
#define For(it,c) for(__typeof(c.begin()) it=c.begin();it!=c.end();++it)
#define reset(a,b) memset(a,b,sizeof(a))
#define mp make_pair
#define dot(a,b) ((conj(a)*(b)).X)
#define X real()
#define Y imag()
#define length(V) (hypot((V).X,(V).Y))
#define vect(a,b) ((b)-(a))
#define cross(a,b) ((conj(a)*(b)).imag())
#define normalize(v) ((v)/length(v))
#define rotate(p,about,theta) ((p-about)*exp(point(0,theta))+about)
#define pointEqu(a,b) (comp(a.X,b.X)==0 && comp(a.Y,b.Y)==0)
#define clrq(x) while(!x.empty()) x.pop();
#define clrvv(v) rep(i,sz(v))v[i].clear();
#define debug(x) cerr << #x << ": " << x << endl;
#define debugv(v) cerr << #v << ": ";For(it,v)cerr <<(*it)<<", "; cerr<<endl;

typedef stringstream ss;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<string> vs;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<vector<int> > vii;
typedef long double ld;
typedef complex<double> point;
typedef pair<point, point> segment;
typedef pair<double, point> circle;
typedef vector<point> polygon;
typedef unsigned long long ull;
typedef long long ll;

//==============================================================
// handling triples
typedef pair<ll,pair<ll,ll> > triple;
#define tfirst first
#define tsecond second.first
#define tthird second.second
#define mt(x,y,z) mp(x,mp(y,z))
//---------------------------------------------------------------

const int oo = (int) 1e9;
const double PI = 2 * acos(0.0);
const double eps = 1e-9;
const int MAXV = 50001, MAXE = 100001;
int head[MAXV], next[MAXE], to[MAXE], from[MAXE];
int parent[MAXV], siz[MAXV], lvl[MAXV], hvyChild[MAXV], hvyRoot[MAXV];
bool isHeavy[MAXE];
int last;
void init(){
 reset(head,-1);
 reset(parent,-1);
 last = 0;
}
void addEdge(int f, int t){
 isHeavy[last] = false;
 parent[t] = last;
 from[last] = f;
 to[last] = t;
 next[last] = head[f];
 head[f] = last++;
}
int dfs(int root, int depth){
 siz[root] = 1;
 lvl[root] = depth;
 hvyChild[root] = -1;
 hvyRoot[root] = root;
 for(int i = head[root]; i != -1; i = next[i])
  siz[root] += dfs(to[i], depth+1);
 for(int i = head[root]; i != -1; i = next[i])
  if(siz[to[i]] >= (siz[root]+1)/2){
   isHeavy[i] = true;
   hvyChild[root] = i;
  }
 return siz[root];
}
void heavyLight(int root = 0){
 dfs(root,0);
 for(int i = 0; i < last; i++){
  if(!isHeavy[i]) continue;
  int f = from[i];
  if(parent[f] == -1 || !isHeavy[parent[f]])
   for(int k = i; k != -1; k = hvyChild[to[k]])
    hvyRoot[to[k]] = f;
 }
}
int LCA(int a, int b){
 while(hvyRoot[a] != hvyRoot[b])
  if(lvl[hvyRoot[a]] > lvl[hvyRoot[b]])
   a = from[parent[hvyRoot[a]]];
  else
   b = from[parent[hvyRoot[b]]];
 if(lvl[a] < lvl[b])
  return a;
 return b;
}
int main(){
 ios_base::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
 freopen("in.txt", "r", stdin);
 //freopen("out.txt", "w", stdout);
#endif
 int n, m;
 while(~scanf("%d", &n)){
  init();
  int u, x, v;
  rep(i,n){
   scanf("%d:(%d)", &u, &x);
   --u;
   rep(k,x){
    scanf("%d", &v);
    --v;
    addEdge(u,v);
   }
  }
  int root = find(parent, parent+n, -1)-parent;
  heavyLight(root);
  scanf("%d", &m);
  vector<int> ans(n,0);
  rep(i,m){
   scanf(" (%d%d)", &u, &v);
   --u,--v;
   int lca = LCA(u,v);
   ans[lca]++;
  }
  rep(i,n){
   if(ans[i]) cout << i+1 << ":" << ans[i]<<endl;
  }
 }

 return 0;
}