#P14107. [ZJCPC 2017] Binary Tree Restoring

[ZJCPC 2017] Binary Tree Restoring

题目描述

Given two depth-first-search (DFS) sequences of a binary tree, can you find a binary tree which satisfies both of the DFS sequences?

Recall that a binary tree is a tree in which each vertex has at most two children, and the depth-first search is a tree traversing method which starts at the root and explores as far as possible along each branch before backtracking.

输入格式

There are multiple test cases. The first line of input contains an integer TT, indicating the number of test cases. For each test case:

The first line contains an integer nn (1n1051 \le n \le 10^5), indicating the number of vertices in the binary tree.

The second line contains nn integers a1,a2,,ana_1,a_2,\dots,a_n (1ain1 \le a_i \le n, 1i<jn,aiaj\forall 1 \le i < j \le n, a_i \ne a_j), indicating the first DFS sequence of the binary tree.

The third line of each test case contains nn integers b1,b2,,bnb_1,b_2,\dots,b_n (1bin1 \le b_i \le n, 1i<jn,bibj\forall 1 \le i < j \le n, b_i \ne b_j), indicating the second DFS sequence of the binary tree.

It is guaranteed that the sum of nn over all test cases does not exceed 10610^6, and there always exists at least one possible binary tree.

We kindly remind you that this problem contains large I/O file, so it's recommended to use a faster I/O method. For example, you can use scanf/printf instead of cin/cout in C++.

输出格式

For each test case, output one line which contains nn integers seperated by one space. The ii-th integer indicates the father of the ii-th vertex in the binary tree which satisfies both of the DFS sequence. If the ii-th vertex is the root of the binary tree, output 00 as its father. If there are multiple valid answers, you can output any of them.

Please, DO NOT print extra spaces at the end of each line, or your program may get a "wrong answer" verdict as this problem is special judged.

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