All submissions for this problem are available.
Appu recently went trekking with her friends. During the trek, she saw a strange kind of tree in the middle of the forest. It can be described as follows -
A Binary Search Tree, is a node-based binary tree data structure which has the following properties:
The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
The left and right subtree each must also be a binary search tree. There must be no duplicate nodes.
To insert a given node in Binary Search Tree, we first compare it with root. If key is greater than root’s key, we recur for right subtree of root node. Otherwise we recur for left subtree. Once a leaf node is found, the new node is added as a child of the leaf node.
Intrigued by the tree, Appu decided to solve a problem concerning it. The Binary Search Tree she saw is of size n rooted at R, which contains all numbers in the range [1,n] (Both inclusive).
Help Appu find the different number of permutations of first n natural numbers which are compatible with given Binary Search Tree.
A permutation is said to be compatible with given BST if it constructs the same BST when nodes are inserted to an empty BST according to the permutation ordering.
The first line of the input contains an integer n denoting the size of the array.The second line of the input contains an integer R denoting the root of the Binary Search Tree.Next n-1 lines contain 2 space saperated integers u, v denoting the edge (u->v) of the tree.
Output a single integer corresponding to the number of different ways of constructing the given Binary Search Tree (modulo 109+7).
- 1 ≤ n ≤ 100000
- 1 ≤ R ≤ n
- 1 ≤ u ≤ n
- 1 ≤ v ≤ n
Input: 3 2 2 1 2 3 Output: 2
ExplanationIf the elements are added to an empty BST in the order according to the permutations [2,1,3] and [2,3,1],they construct the given Binary Search Tree.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS|
Fetching successful submissions