• 博客访问： 1140350
• 博文数量： 196
• 博客积分： 4141
• 博客等级： 中将
• 技术积分： 2253
• 用 户 组： 普通用户
• 注册时间： 2009-03-21 20:04

2019年（31）

2016年（1）

2014年（16）

2011年（8）

2010年（25）

2009年（115）

2009-06-17 15:59:01

Count Common Ancestors

 Time Limit:6s Memory limit:32M Accepted Submit:74 Total Submit:349

This problem is very simple and well known.
It is shown as follows:
There is a tree which has n nodes, and the nodes are numbered from 1 to n, No. 1 is always the root of the tree. Given you two nodes of the tree, you should count the total number of their common ancestors.

### Input

There are mulitiple tests. For each test, the first line is an integer n(1<=n<=50000), following n lines, the i+1-th line denotes the information of the i-th node. For each line, there is an integer k(0<=k<=n-1), denoting the number of direct children of the i-th node. Then following k integers, denoting the No. of the i-th node. When k is equal to 0, denoting the i-th node is leaf node. You should note that the node can be the ancestor of itself.
The n+2-th line is an integer m (1<=m<=30,000), denoting there are m queries. Following m lines, for each line, there are two integers x and y, denoting the No. of the two nodes.

### Output

For each query, you should count the total number of their common ancestors.

### Sample Input

`123 2 3 42 5 6002 7 82 9 100002 11 120063 117 124 89 128 101 12`

### Sample Output

`121321`

 ```/*   Name: tarjan 算法求 LCA   Author: Micklongen   Description: O(N + Q)，N表示节点数，Q表示查询数 */ #include #include #include #include using namespace std; struct Node {     int visit;     int child;     int depth;     int brother; }; struct Node node[50010]; struct List_node {     int index;     int node;     int next; }; int header[50010]; struct List_node list_node[100010]; int top; int out[50010]; int father[50010]; int find(int u) {     return father[u] == u ? u : (father[u] = find(father[u])); } int merge(int u, int v) {     int a = find(u);     int b = find(v);     if (a != b)         father[b] = a;     return 0; } int com_depth(int root, int depth) {     int child, list;     node[root].depth = depth;     child = node[root].child;     father[root] = root;     while(child != -1)     {         com_depth(child, depth + 1);         merge(root, child);         child = node[child].brother;     }     node[root].visit = 1;     list = header[root];     while (list != -1)     {         if (node[list_node[list].node].visit == 1)             out[list_node[list].index] = node[find(list_node[list].node)].depth;         list = list_node[list].next;     }     return 0; } int main() {     int i, j;     int v, num, inum;     int a, b;     while (scanf("%d", &num) != EOF)     {         for (i = 1; i <= num; ++i)         {             header[i] = -1;             node[i].child = -1;             node[i].visit = 0;             scanf("%d", &inum);             for (j = 1; j <= inum; ++j)             {                 scanf("%d", &v);                 node[v].brother = node[i].child;                 node[i].child = v;             }         }         top = 0;         scanf("%d", &num);         for (i = 1; i <= num; ++i)         {             scanf("%d %d", &a, &b);             list_node[top].index = i;             list_node[top].node = b;             list_node[top].next = header[a];             header[a] = top;             ++top;             list_node[top].index = i;             list_node[top].node = a;             list_node[top].next = header[b];             header[b] = top;             ++top;         }         com_depth(1, 1);         for (i = 1; i <= num; ++i)             printf("%d\n", out[i]);     }     return 1; } ```