Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1294507
  • 博文数量: 196
  • 博客积分: 4141
  • 博客等级: 中将
  • 技术积分: 2253
  • 用 户 组: 普通用户
  • 注册时间: 2009-03-21 20:04
文章存档

2019年(31)

2016年(1)

2014年(16)

2011年(8)

2010年(25)

2009年(115)

分类:

2009-06-21 22:04:42

Binary Search Tree II

Time Limit:1sMemory limit:32M
Accepted Submit:29Total Submit:108

The binary search tree (BST) is defined in the former problem “binary search tree”

Now, also use a lot of disparate integers to build a binary search tree. But we has knew the shape of the BST, please tell me how many orders these integers could be in?

Input

The input will contain several test cases. Each test case begins with an integer N(1≤n≤1000), and N lines follows, each line contains three integers A, B, and C(the tree node ID are numbered from 1 to N), denote the node A has left children B and right children C. if B or C equals to 0,the node A’s corresponding position has no children.

The node with ID 1 is always the root of the BST.

Output

The answer mod 5087.

Sample Input

4
1 2 3
2 0 4
3 0 0
4 0 0

Sample Output

3

Hint

The ID orders can be in follow:
1 2 3 4
1 2 4 3
1 3 2 4

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N 1001

struct Node
{
    int lchild;
    int rchild;
};
struct Node node[1010];

int result;

int C[N][N];

int tree(int root)
{
    int a, b;

    if (root == 0)
        return 0;

    a = tree(node[root].lchild);
    b = tree(node[root].rchild);

    result = result * C[a + b][a];
    result %= 5087;

    return a + b + 1;
}

int main()
{
    int i, j, test;
    int v;

    for (i = 0; i < N; i++) C[i][0] = C[i][i] = 1;
    for (i = 1; i < N; i++)
        for (j = 1; j < i; j++)
            C[i][j] = (C[i-1][j] + C[i-1][j-1]) % 5087;

    while (scanf("%d", &test) != EOF)
    {
        for (i = 1; i <= test; ++i)
        {
            scanf("%d", &v);
            scanf("%d %d", &node[v].lchild, &node[v].rchild);
        }

        result = 1;
        tree(1);
        printf("%d\n", result);
    }

    return 0;
}

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