hi,
i’m trying to solve this lca problem in spoj SPOJ.com - Problem LCA . I’m using the http://help.topcoder.com/data-science/competing-in-algorithm-challenges/algorithm-tutorials/range-minimum-query-and-lowest-common-ancestor/#Another easy solution in O(N logN, O(logN)
method to fing the lca. but i’m getting a wrong answer. Please have a look at my code.
class FMain {
static FMain.Parser sc = new Parser(System.in);
static PrintWriter out = new PrintWriter(System.out, true);
public static void main(String[] args) throws Exception {
int t = sc.nextInt();
while(t-->0){
int n = sc.nextInt(),T[] = new int[n+1];
for(int i = 1 ; i <= n ; i++){
int m = sc.nextInt();
while(m-->0)
T[sc.nextInt()] = i;
}
int P[][] = new int[n+1][31];
//the first ancestor of every node i is T[i]
for (int i = 1; i <= n; i++)
P[i][0] = T[i];
//bottom up dynamic programing
for (int j = 1; 1 << j <= n; j++)
for (int i = 1; i <= n; i++)
if (P[i][j - 1] != 0)
P[i][j] = P[P[i][j - 1]][j - 1];
int root = -1,L[] = new int[n+1] ;
for(int i = 1 ; i <= n ; i++ ) if(T[i] == 0){
root = i;
break;
}
// For finding the level of each node
Queue<Integer> qu = new LinkedList<Integer>();qu.add(root);
for(int i = 0 ; !qu.isEmpty() ; i++){
int size = qu.size();
while(size-->0){
int now = qu.remove();
L[now] = i;
for(int j = 1 ; j <= n ; j++)if(T[j] == now) qu.add(j);
}
}
int qq = sc.nextInt();
while(qq-->0){
int p = sc.nextInt(),q = sc.nextInt();
if(p == q){
out.println(p);
continue;
}
int tmp, log, i;
//if p is situated on a higher level than q then we swap them
if (L[p] < L[q]){
tmp = p; p = q; q = tmp;
}
//we compute the value of [log(L[p)]
for (log = 1; 1 << log <= L[p]; log++);
// log--;
//we find the ancestor of node p situated on the same level
//with q using the values in P
for (i = log; i >= 0; i--)
if (L[p] - (1 << i) >= L[q]){
p = P[p][i];
}
//we compute LCA(p, q) using the values in P
if(p == q)
out.println(p);
else{
for (i = log; i >= 0; i--)
if (P[p][i] != 0 && P[p][i] != P[q][i]){
p = P[p][i]; q = P[q][i];
}
out.println(T[p]);
}
}
}
out.close();
}