[ADV 05] Common Ancestor

You are to find the closest common ancestor of two vertices in a binary tree.
For example, the common ancestors of vertices 8 and 13 in the figure below ar
e vertices 3 and 1. Among them, vertex 3 is the closest to the vertex 8 and 1
3. And the size of sub-tree (the number of vertices in the sub-tree) rooted b
y vertex 3 is 8.

Given a binary tree and two vertices, write a program that finds the closest
common ancestor and computes the size of the sub-tree rooted by the closest c
ommon ancestor. No input is given where one of the two given vertices is an a
ncestor of the other. For example, ‘11 and 3’ in the above tree is an invalid
input. Therefore, your program does not have to consider this case.

一个节点是另一个节点祖先的情况不会出现，所以不用考虑。

[Constraints]

The number of vertices are from 3 to 10000

 

[Input]
You are given 10 test cases. Each test case has two lines, so the total numbe
r of lines is 20. In each test case, the first line consists of four integers,
V (the number of vertices in the tree), E (the number of edges), and the indi
ces of two vertices. E edges are listed in the next line. Each edge is repres
ented by two vertices; the index of the parent vertex always precedes the ind
ex of the child. For example, the edge connecting vertices 5 and 8 is represe
nted by “5 8”, not by “8 5.” There is no order in which the edges are given.
Every consecutive integer in the input is separated by a space.

Given 10 test cases,

First 4 test cases contain small number of vertices(3, 5, 7, 10 each).

Next 6 test cases contain same or greater than 50 vertices.

The indices of vertices are integers from 1 to V, and root vertex always has
the index 1.父亲的节点编号总是比孩子节点的编号小。

It is guaranteed that the parent vertex has smaller index than the child vertex.

In this problem, it is not important whether the child is the left child of t
he parent or the right child; so you can decide this arbitrarily.

 

[Output]
Output 10 answers in 10 lines. Each line starts with ‘#x’ meaning the index o
f a test case, and writes the answer after a space. The answer has two intege
rs: the index of the closest common ancestor and the size of the sub-tree roo
ted by the closest common ancestor. These two integers are separated by a spa
ce as well.

 

[I/O Example]

Input (20 lines in total)

13 12 8 13 ← Start of the first input

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

10 9 1 10 ← Start of the second input

1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10

...

Output (10 lines in total)

#1 3 8

#2 1 10

...

-----------------------------------------------------------------------------
Code Begin

#include <stdio.h>
#include <queue>

#ifdef LOCAL_DEBUG
#pragma warning(disable : 4996)
#endif

#define node_num 10000

struct node
{
    int p, s1, s2;
};

struct node tree[node_num];
int cnt;

int LCA(int p1, int p2)
{
    int pos, len1 = 1, len2 = 1, frt1, frt2;
    std::queue <int> q1, q2;

    pos = p1;
    q1.push(pos);
    while (pos != 1)
    {
        pos = tree[pos].p;
        q1.push(pos);
        len1++;
    }
    pos = p2;
    q2.push(pos);
    while (pos != 1)
    {
        pos = tree[pos].p;
        q2.push(pos);
        len2++;
    }

    while (len1 > len2)
    {
        q1.pop();
        len1--;
    }
    while (len2 > len1)
    {
        q2.pop();
        len2--;
    }

    while (1)
    {
        frt1 = q1.front();
        frt2 = q2.front();
        if (frt1 == frt2)
        {
            pos = frt1;
            break;
        }

        q1.pop();q2.pop();
    }

    return pos;
}

void count(int pt)
{
    cnt++;

    if (tree[pt].s1 != 0)
    {
        count(tree[pt].s1);
    }

    if (tree[pt].s2 != 0)
    {
        count(tree[pt].s2);
    }
}

int main()
{
    int test_case;
    int T;

#ifdef LOCAL_DEBUG
    freopen("test_input.txt", "r", stdin);
    freopen("sample_output.txt", "w", stdout);
#endif

    setbuf(stdout, NULL);
    scanf("%d", &T);

    for (test_case = 1; test_case <= T; test_case++)
    {
        int i, n, e, p1, p2, temp1, temp2, ans;

        scanf("%d %d %d %d", &n, &e, &p1, &p2);
        for (i = 0; i < n; i++)
        {
            tree[i].p = 0;tree[i].s1 = 0; tree[i].s2 = 0;
        }
        for (i = 0; i < e; i++)
        {
            scanf("%d %d ", &temp1, &temp2);
            if (tree[temp1].s1 == 0)
            {
                tree[temp1].s1 = temp2;
            }
            else
            {
                tree[temp1].s2 = temp2;
            }

            tree[temp2].p = temp1;
        }

        ans = LCA(p1, p2);
        cnt = 0;
        count(ans);

        printf("#%d %d %d\n", test_case, ans, cnt);
    }

    return 0;
}

Code End

Code Using My Que

#include <stdio.h>
#define NODE_NB 10000
#define QUE_SZ 10000
#define LOCAL_DEBUG
typedef struct{
    int hd;
    int tl;
    int nd[QUE_SZ];
}QUE;

int que_init(QUE *q);
int que_empty(QUE *q);
int que_full(QUE *q);
int que_head(QUE *q);
int que_tail(QUE *q);
int pop_head(QUE *q);
int push_tail(QUE *q,int n);
int que_clr(QUE *q);
int que_size(QUE *q);
int que_init(QUE *q)
{
    if(NULL==q)
        return -1;
    q->hd=0;
    q->tl=0;
    return 0;
}

/*
 int que_emtpy(QUE *q)
 {
 return q->hd==q->tl;
 }
 */
int que_full(QUE *q)
{
    return (q->tl+1)%QUE_SZ==q->hd;
}

int que_head(QUE *q)
{
    if(q->hd!=q->tl)
        return q->nd[q->hd];
    return -1;
}

int que_tail(QUE *q)
{
    int i;
    if(q->hd!=q->tl){
        i=(q->tl+QUE_SZ-1)%QUE_SZ;
        return q->nd[i];
    }
    return -1;
}

int pop_head(QUE *q)
{
    int data=-1;
    if(q->hd!=q->tl){
        data=q->nd[q->hd];
        q->hd=(q->hd+1)%QUE_SZ;
    }
    return data;
}
int push_tail(QUE *q,int n)
{
    if(que_full(q))
        return -1;
    q->nd[q->tl]=n;
    q->tl=(q->tl+1)%QUE_SZ;
    return 1;
}

int que_clr(QUE *q)
{
    if(q->hd==q->tl)
        return 0;
    q->hd=0;
    q->tl=0;
    return 0;
}

int que_size(QUE *q)
{
    return (q->tl-q->hd+QUE_SZ)%QUE_SZ;
}

typedef struct node
{
    int p, s1, s2;
}NODE;

NODE tree[NODE_NB];
int cnt;

int LCA(int p1, int p2)
{
    int pos, len1 = 1, len2 = 1, frt1, frt2;
    QUE q1, q2;

    pos = p1;
    push_tail(&q1,pos);
    while (pos != 1)/* */
    {
        pos = tree[pos].p;
        push_tail(&q1, pos);
        len1++;
    }
    pos = p2;
    push_tail(&q2,pos);
    while (pos != 1)
    {
        pos = tree[pos].p;
        push_tail(&q2,pos);
        len2++;
    }

    while (len1 > len2)
    {
        pop_head(&q1);
        len1--;
    }
    while (len2 > len1)
    {
        pop_head(&q2);
        len2--;
    }

    while (1)
    {
        frt1 = que_head(&q1);
        frt2 = que_head(&q2);
        if (frt1 == frt2)
        {
            pos = frt1;
            break;
        }

        pop_head(&q1);
        pop_head(&q2);
    }

    return pos;
}

void count(int pt)
{
    cnt++;

    if (tree[pt].s1 != 0)
    {
        count(tree[pt].s1);
    }

    if (tree[pt].s2 != 0)
    {
        count(tree[pt].s2);
    }
}

int main(int argc, const char * argv[])
{
    int test_case;
    int T;

#ifdef LOCAL_DEBUG
    freopen("test_input.txt", "r", stdin);
    freopen("adv05_o.txt", "w", stdout);
#endif

    setbuf(stdout, NULL);
    scanf("%d", &T);

    for (test_case = 1; test_case <= T; test_case++)
    {
        int i, n, e, p1, p2, temp1, temp2, ans;

        scanf("%d %d %d %d", &n, &e, &p1, &p2);
        for (i = 0; i < n; i++)
        {
            tree[i].p = 0;tree[i].s1 = 0;tree[i].s2 = 0;
        }
        for (i = 0; i < e; i++)
        {
            scanf("%d %d ", &temp1, &temp2);
            if (tree[temp1].s1 == 0)
            {
                tree[temp1].s1 = temp2;
            }
            else
            {
                tree[temp1].s2 = temp2;
            }

            tree[temp2].p = temp1;
        }

        ans = LCA(p1, p2);
        cnt = 0;
        count(ans);

        printf("#%d %d %d\n", test_case, ans, cnt);
    }

    return 0;
}

Code Using My Que






成大事只要一点勇气