strict      

A binary tree is considered strict if all its internal nodes have exactly two children.
A set of n strict binary trees is given, each tree having m nodes numbered from 1 to m.
We recurrently define the equality between two trees as having fixed roots in nodes x, and respectively y.

A(x) = A(y) if:

  • x,y have no children

    • or
  • x,y have chilfren, A(right_child(x)) = A(right_child(y)) and A(left_child(x)) = A(left_child(y))

    • (where we noted as A(x) the tree with a root x)

    In the same way we can define the "<" order relationship

    A(x) < A(y) if:
  • x has no children and y has children
    or

  • nodes x and y have children and A(left_child(x)) < A(left_child(y))

    • or
  • nodes x and y have children, A(left_child(x)) = A(left_child(y)) and A(right_child(x)) < A(right_child(y))

    • Task
    Determine the length of the longest increasing subsequence (not necessarily strict) of trees from the given set, considering the order relationship defined above.

    Input Data
    Input file strict.in has the following structure:   
    - line one contains two positive integers separated by a space n m, representing the number of trees and, respectively, the size of the trees
    - each of the following n lines contains m - 1 + (m + 1) / 2 numbers; line i + 1 contains required information for tree i as follows: for every node from 1 to m it contains a 0 if the node has no children or two numbers representing the left and, respectively, the right child; first node 1 is described, then node 2, etc. Line: 0 0 5 1 0 0 7 3 2 4 means that nodes 1 and 2 have no children, node 3 has as a left child node 5 and as a right child node 1, node 4 has no children, and so on.

    Output Data
    Output file strict.out will contain a single number representing the length of the longest increasing subsequence.

    Constraints
    0 < n <= 10000
    0 < m <= 51
     Champions can realize why in a strict binary tree there is only one node which can fulfill the role of tree root. Due to this, the relationship is well defined.
    40% of the tests will have n <= 5000 and m <= 31.
    Participants are encouraged to use functions like fgets() or fread() to read data.
    Be there x=(x1, x2, ..., xn) a sequence of n elements. A subsequence of x is comprised of elements from x, in the order in which they appear in x (xi1, xi2, ..., xik with i1<i2<...<ik).

    Example

    strict.in strict.out Explanation

    5 7
    0 0 5 1 0 0 7 3 2 4
    3 7 6 4 0 1 5 0 0 0
    7 5 0 0 0 6 3 0 2 4
    4 3 0 0 5 6 0 0 2 1
    2 5 3 4 0 7 6 0 0 0

    		 3

    A solution can be represented by trees 2, 3 and 5

    Time limit: 0.1 seconds/test

    Iolanda Popa
    student - Faculty of Informatics, Iasi
    Contact: iolivp@gmail.com