Problem D: Tree Number Problem D: Tree Number
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 717 Solved: 262
[Submit][Status][Web Board]Description
Given the order of a tree's pre-order traversal and post-order traversal, you are asked to find out how many distinct binary trees fit the given traversal orders.
Input
The first line contains one integer \(T\), which denotes the number of the test cases \((1\le T\le 10\ 000)\). The nodes of a binary tree are represented by capital letters, and no two distinct nodes are represented with the same letter.
In each case, the first line contains a string \(S_{pre}\), denoting the access order of the pre-order traversal. The second line contains a string \(S_{post}\), denoting the access order of the post-order traversal \((|S_{pre}|, |S_{post}|\le 26)\).
Output
Output the number of binary trees which meet the requirements.
Sample Input
1
ABCD
DCBA
Sample Output
8
HINT
[Submit][Status]