# Garance's solution, the solution are correct # but with the recursive implementation it takes more # than 1m to run on the last test cases. from dataclasses import dataclass NONE_NODE = -1 NOT_GIVEN = 0 PRIME = 999999937 INFINITE_DEPTH = 500001 def power_modulo_prime(a, b): if b == 0: return 1 if b % 2 == 0: return power_modulo_prime(a * a % PRIME, b // 2) else: return a * power_modulo_prime(a, b - 1) % PRIME def mod_inverse(a): return power_modulo_prime(a, PRIME - 2) def combination_modulo_prime(a, b): if a < 0 or b > a or b < 0: return 0 res = 1 for i in range(1, b + 1): res = res * (a - i + 1) % PRIME res = res * mod_inverse(i) % PRIME return res @dataclass class Node: label: int depth: int subtree_size: int parent: int left_child: int right_child: int only_child: int determinate: bool = False class PartialTree: def __init__(self, N, pre_order, post_order, in_order): self.N = N self.pre_order = pre_order self.post_order = post_order self.index_in_post_order = [0] * (self.N + 1) for i, e in enumerate(post_order): self.index_in_post_order[e] = i self.index_in_in_order = [0] * (self.N + 1) for i, e in enumerate(in_order): self.index_in_in_order[e] = i self.in_order = in_order self.nodes = [None] * (self.N + 1) self.root = pre_order[0] self.construct_node(0, pre_order, post_order, 0, NONE_NODE) def get_flexible_nodes(self): # just for debugging for node in self.nodes[1:]: if node.only_child != NONE_NODE: yield node.label def construct_node(self, depth, pre_order, post_order, current_post_order, parent): assert len(pre_order) == len(post_order) subtree_size = len(pre_order) if subtree_size == 0: return root = pre_order[0] if subtree_size == 1: # Leaf self.nodes[root] = Node( root, depth, subtree_size, parent, NONE_NODE, NONE_NODE, NONE_NODE ) elif pre_order[1] == post_order[-2]: # Only child = flexible, the child can be right or left self.nodes[root] = Node( root, depth, subtree_size, parent, NONE_NODE, NONE_NODE, pre_order[1] ) self.construct_node( depth + 1, pre_order[1:], post_order[:-1], current_post_order, root ) else: # Two children left_child = pre_order[1] size_left_substree = ( self.index_in_post_order[left_child] - current_post_order + 1 ) right_child = pre_order[size_left_substree + 1] self.nodes[root] = Node( root, depth + 1, subtree_size, parent, left_child, right_child, NONE_NODE, ) self.construct_node( depth + 1, pre_order[1 : size_left_substree + 1], post_order[:size_left_substree], current_post_order, root, ) self.construct_node( depth + 1, pre_order[size_left_substree + 1 :], post_order[size_left_substree:-1], current_post_order + size_left_substree, root, ) def highest_knowed_node(self): min_depth = INFINITE_DEPTH highest_node = 0 for index in self.in_order: if index == 0: continue if min_depth > self.nodes[index].depth: highest_node = index min_depth = self.nodes[index].depth return self.nodes[highest_node] def determinate_ancestor(tree, node): if not node.determinate: node.determinate = True determinate_ancestor(tree, tree.nodes[node.parent]) def determinate_other_inorder_knowed(tree): for index in tree.in_order: if tree.nodes[index] != None: # ancestor from a knowed node are determinate # appart from the highest node which has special computation determinate_ancestor(tree, tree.nodes[index]) def analyse_ancestors(tree, node): # returns the leftmost possition of the node in the inorder # (only considering its ancestors) and the number of flexible # nodes in its ancestors # The processing of this node will be accounted for node.determinate = True if node.parent == NONE_NODE: # node is the root return 0, 0 parent = tree.nodes[node.parent] index, nb_flexible_nodes = analyse_ancestors(tree, parent) if parent.right_child == node.label: # node is right node we shift by the size of the left subtree left_subtree_size = tree.nodes[parent.left_child].subtree_size return (index + left_subtree_size + 1, nb_flexible_nodes) elif parent.only_child == node.label: # parent is flexible return (index, nb_flexible_nodes + 1) return (index, nb_flexible_nodes) def compute_possibilities_for_in_order(tree): # closest node to the root knowned in inorder highest_node = tree.highest_knowed_node() if highest_node != None: # at least one node is given in the inorder # determinate the node with one child that are fixed as (l/r) by the inorder leftmost_index, nb_flexible_above = analyse_ancestors(tree, highest_node) determinate_other_inorder_knowed(tree) nb_undeterminate = 0 for node in tree.nodes[1:]: # all nodes with zero or two children are determinate if not node.determinate and node.only_child != NONE_NODE: nb_undeterminate += 1 # we have no info it (l/r) child # number of possibilities added by the undeterminate nodes res = power_modulo_prime(2, nb_undeterminate) # if no info on the inorder all only child are undetermined if highest_node == None: return res # For the nodes above the highest node, they modify the index # of the highest in the inorder, we compute the number of # combinations that give the actual position in the in_order actual_index = tree.index_in_in_order[highest_node.label] combination_above = 0 # if the highest node has only one child, whether it is (l/r) also # afects the index in the inorder if highest_node.only_child != NONE_NODE: only_child = tree.nodes[highest_node.only_child] if only_child.determinate: if actual_index > 0 and tree.in_order[actual_index - 1] != NOT_GIVEN: # a descendant is at the right therefore only child is a left child # This works because we are working on consecutive and looking at the highest node highest_node.left_child = only_child.label else: # the only child can be a right child or left child diff_right = actual_index - leftmost_index combination_above = combination_modulo_prime(nb_flexible_above, diff_right) highest_node.left_child = only_child.label # for the lefmost pos we account for a left child subtree if there is one if highest_node.left_child != NONE_NODE: leftmost_index += tree.nodes[highest_node.left_child].subtree_size diff = actual_index - leftmost_index combination_above += combination_modulo_prime(nb_flexible_above, diff) res = res * combination_above % PRIME return res def main(): # Input parsing N = int(input()) pre_order = [int(i) for i in input().split()] post_order = [int(i) for i in input().split()] in_order = [int(i) for i in input().split()] tree = PartialTree(N, pre_order, post_order, in_order) print(compute_possibilities_for_in_order(tree)) if __name__ == "__main__": main()