Binary Search Tree II

Binary Search Tree II

---

Time Limit:1s	Memory limit:32M
Accepted Submit:29	Total 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;
}