Chinaunix首页 | 论坛 | 博客
  • 博客访问: 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:6sMemory limit:32M
Accepted Submit:74Total 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

12
3 2 3 4
2 5 6
0
0
2 7 8
2 9 10
0
0
0
2 11 12
0
0
6
3 11
7 12
4 8
9 12
8 10
1 12

Sample Output

1
2
1
3
2
1





/*
  Name: tarjan 算法求 LCA
  Author: Micklongen
  Description: O(N + Q),N表示节点数,Q表示查询数
*/


#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <algorithm>

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;
}

阅读(1608) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~