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.
Input. The first line will be the number of test cases. Each
test case will start with a number n (1
≤ n ≤ 1000) the number of nodes in the tree. Nodes are
numbered from 1 to n. The next n lines each one will start with a
number m (0 ≤ m ≤ 999) the number of child nodes of the n-th node, followed by m numbers the child nodes of the n-th node. The next line will be a
number q (1 ≤ q ≤ 1000) the number of queries you have to answer for the
given tree t. 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 ≤ 1000).
Input will guarantee that there is only one root and no
cycles.
Output. 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.
|
Sample Input |
Sample Output |
|
1 7 3 2 3 4 0 3 5 6 7 0 0 0 0 2 5 7 2 7 |
Case 1: 3 1 |
LCA
Çàäàíî
äåðåâî ñ êîðíåì â âåðøèíå 1. Íåîáõîäèìî îòâåòèòü íà LCA çàïðîñû.
Ðåàëèçàöèÿ
àëãîðèòìà
#include <cstdio>
#include <vector>
#define MAX 1001
using namespace
std;
int n, l, u, v, i, j, q, edges, ts,
tests;
vector<int> g[MAX];
int timer, d[MAX], f[MAX];
int up[MAX][10];
void dfs (int
v, int p = 1)
{
int i, to;
d[v] = timer++;
up[v][0] = p;
for(i = 1; i <= l; i++)
up[v][i] =
up[up[v][i-1]][i-1];
for(i = 0; i < g[v].size(); i++)
{
to = g[v][i];
if (to != p) dfs (to, v);
}
f[v] = timer++;
}
// if a is a parent of b
int Parent(int
a, int b)
{
return (d[a] <= d[b]) && (f[a] >=
f[b]);
}
int LCA (int
a, int b)
{
if (Parent(a, b)) return
a;
if (Parent(b, a)) return
b;
for (int i = l; i
>= 0; i--)
if (!Parent(up[a][i], b)) a = up[a][i];
return up[a][0];
}
int main(void)
{
scanf("%d",&tests);
for(ts = 1; ts <= tests; ts++)
{
printf("Case %d:\n",ts);
scanf("%d",&n);
for(i = 0; i <= n; i++) g[i].clear();
for(i = 1; i <= n; i++)
{
scanf("%d",&edges);
for(j = 0; j < edges; j++)
{
scanf("%d",&v);
g[i].push_back(v); g[v].push_back(i);
}
}
l = 1;
while ((1 << l) <= n + 1) l++;
dfs(1);
scanf("%d",&q);
for(i = 0; i < q; i++)
{
scanf("%d %d",&u,&v);
printf("%d\n",LCA(u,v));
}
}
return 0;
}