# Garance's solution. Converted to iterative by Raphael. from dataclasses import dataclass import sys 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 def highest_knowed_node(): min_depth = INFINITE_DEPTH highest_node = 0 for index in in_order: if index == 0: continue if min_depth > tree[index].depth: highest_node = index min_depth = tree[index].depth return tree[highest_node] 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(highest_node): # returns the leftmost possition of the node in the inorder # (only considering its ancestors) and the number of flexible # nodes in its ancestors current_node = highest_node index, nb_flexible_above = 0, 0 while current_node.parent != NONE_NODE: # node is not the root # The processing of this node will be accounted for current_node.determinate = True parent = tree[current_node.parent] if parent.right_child == current_node.label: # node is right node we shift by the size of the left subtree left_subtree_size = tree[parent.left_child].subtree_size index += left_subtree_size + 1 elif parent.only_child == current_node.label: # parent is flexible nb_flexible_above += 1 current_node = parent # continue exploring ancestors current_node.determinate = True # root accounted for return (index, nb_flexible_above) def determinate_other_inorder_knowed(): for index in in_order: if index != NOT_GIVEN: # ancestor from a knowed node are determinate # appart from the highest node which has special computation current_node = tree[index] while not current_node.determinate: current_node.determinate = True current_node = tree[current_node.parent] def compute_possibilities_for_in_order(): # closest node to the root knowned in inorder highest_node = highest_knowed_node() if highest_node != NONE_NODE: # 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(highest_node) determinate_other_inorder_knowed() nb_undeterminate = 0 for node in tree[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_NODE: 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 = 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[highest_node.only_child] if only_child.determinate: if actual_index > 0 and 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[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 # Parse input 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()] # Create indexes index_in_post_order = [0] * (N + 1) for i, e in enumerate(post_order): index_in_post_order[e] = i index_in_in_order = [0] * (N + 1) for i, e in enumerate(in_order): index_in_in_order[e] = i root = pre_order[0] tree = [NONE_NODE] * (N + 1) @dataclass class StackElmt: # params depth: int parent: int pre_start: int pre_end: int post_start: int post_end: int def iterative_construct_nodes(): stack = [StackElmt(0, NONE_NODE, 0, N - 1, 0, N - 1, )] while stack: top = stack[-1] del stack[-1] assert top.pre_end - top.pre_start == top.post_end - top.post_start subtree_size = top.pre_end - top.pre_start + 1 if subtree_size == 0: continue node = pre_order[top.pre_start] if subtree_size == 1: # leaf tree[node] = Node( node, top.depth, subtree_size, top.parent, left_child=NONE_NODE, right_child=NONE_NODE, only_child=NONE_NODE, ) elif pre_order[top.pre_start + 1] == post_order[top.post_end - 1]: # Only child, the child can be right or left tree[node] = Node( node, top.depth, subtree_size, top.parent, left_child=NONE_NODE, right_child=NONE_NODE, only_child=pre_order[top.pre_start + 1], ) stack.append(StackElmt( depth=top.depth + 1, parent=node, pre_start=top.pre_start + 1, pre_end=top.pre_end, post_start=top.post_start, post_end=top.post_end - 1,)) else: # Two chidren left_child = pre_order[top.pre_start + 1] left_subtree_size = index_in_post_order[left_child] - top.post_start + 1 right_child = pre_order[top.pre_start + 1 + left_subtree_size] tree[node] = Node( node, top.depth, subtree_size, top.parent, left_child=left_child, right_child=right_child, only_child=NONE_NODE, ) # construct_nodes( # depth + 1, # node, # pre_start + 1, # pre_start + left_subtree_size, # post_start, # post_start + left_subtree_size - 1, # ) stack.append(StackElmt( depth=top.depth + 1, parent=node, pre_start=top.pre_start + left_subtree_size + 1, pre_end=top.pre_end, post_start=top.post_start + left_subtree_size, post_end=top.post_end - 1,)) # construct_nodes( # depth + 1, # node, # pre_start + left_subtree_size + 1, # pre_end, # post_start + left_subtree_size, # post_end - 1, # ) stack.append(StackElmt( depth=top.depth + 1, parent=node, pre_start=top.pre_start + 1, pre_end=top.pre_start + left_subtree_size, post_start=top.post_start, post_end=top.post_start + left_subtree_size - 1,)) #construct_nodes( # depth=0, parent=NONE_NODE, pre_start=0, pre_end=N - 1, post_start=0, post_end=N - 1 #) iterative_construct_nodes() print(compute_possibilities_for_in_order())