SPOJ LCA Lowest Common Ancestor

原题链接

no tags

A tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree. - Wikipedia

The lowest common ancestor (LCA) is a concept in graph theory and computer science. Let T be a rooted tree with N nodes. The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself). - Wikipedia

Your task in this problem is to find the LCA of any two given nodes v and w in a given tree T.

For example the LCA of nodes 9 and 12 in this tree is the node number 3.

The first line of input will be the number of test cases. Each test case will start with a number N the number of nodes in the tree, 1 <= N <= 1,000. Nodes are numbered from 1 to N. The next N lines each one will start with a number M the number of child nodes of the Nth node, 0 <= M <= 999 followed by M numbers the child nodes of the Nth node. The next line will be a number Q the number of queries you have to answer for the given tree T, 1 <= Q <= 1000. The next Q lines each one will have two number v and w in which you have to find the LCA of v and w in T, 1 <= v, w <= 1,000.

Input will guarantee that there is only one root and no cycles.

For each test case print Q + 1 lines, The first line will have “Case C:” without quotes where C is the case number starting with 1. The next Q lines should be the LCA of the given v and w respectively.

Input:

173 2 3 403 5 6 7000025 72 7output:

Case 1:31

#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <queue>#define INF 1e9#define MOD 1000000007#define maxn 1005using namespace std;typedef long long ll;vector<int> v[maxn];int vis[maxn], d[maxn<<2], p[maxn<<2], c[maxn], cnt;int dp[maxn<<2][20];void dfs(int i, int dis, int f){c[i] = cnt;d[cnt] = dis;p[cnt++] = i;for(int j = 0; j < v[i].size(); j++){int h = v[i][j];if(h != f){dfs(h, dis+1, i);d[cnt] = dis;p[cnt++] = i;}}}void RMQ(){for(int i = 0; i < cnt; i++)  dp[i][0] = p[i];for(int i = 1; (1<<i) <= cnt; i++)  for(int j = 0; j+(1<<i) <= cnt; j++){  int k1 = dp[j][i-1], k2 = dp[j+(1<<(i-1))][i-1];  int ans = k2;  if(d[c[k1]] < d[c[k2]])   ans = k1;  dp[j][i] = ans;  }  }int main(){//freopen("in.txt", "r", stdin);int t, cas = 0;scanf("%d", &t);while(t--){cnt = 0;int n, m, a, b;scanf("%d", &n);memset(vis, 0, sizeof(vis));for(int i = 1; i <= n; i++)  v[i].clear();for(int i = 1; i <= n; i++){scanf("%d", &m);for(int j = 0; j < m; j++){scanf("%d", &a);vis[a] = 1;v[i].push_back(a);}}for(int i = 1; i <= n; i++){if(vis[i] == 0){dfs(i, 0, -1);break;}}RMQ();int q;scanf("%d", &q);printf("Case %d:\n", ++cas);while(q--){scanf("%d%d", &a, &b);int p1 = c[a], p2 = c[b];if(p1 > p2) swap(p1, p2);int r = 0;while(1<<(r+1) <= p2-p1+1) r++; int k1 = dp[p1][r], k2 = dp[p2-(1<<r)+1][r];if(d[c[k1]] < d[c[k2]])  printf("%d\n", k1);else printf("%d\n", k2);}}return 0;}