Description

Just as the title, you will be given a pre-order traversal of BST, please print the post-order traversal of it.

(BST is a tree that the number of each node will be larger than its left subtree, and smaller than its right subtree.)

 

Think 1: Is binary search useful in this problem?

Think 2: Is it possible not to build the tree?

 

hint1: just by looking at the sequence, can you find which are in the left subtree, which are in the right subtree?

hint2: the left subtree and the right subtree are both a tree, don't you think it sounds familiar? (recur...)

hint3: is there any way that we can find the beginning of the right subtree quickly?

Input

The first line contains one integer N, means there are n node in this tree. 

The next line has N different integers, which is the pre-order traversal of the BST. Each number is between [1, 1e9].

For testcase 1~3: 1 <= N <= 1e4.

For testcase 4~6: 1 <= N <= 2e5.

Output

Print the post-order of the BST.

Notice: print a space after each number and DO NOT print '\n' at last.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The Traveling Salesman Problem (TSP) is a classical problem that we are to find the shortest distance traversing all vertices in a graph from any source and returning to the source, which is considered hard for computers (and maybe human as well).

Nevertheless, the TSP on tree is quite easy: the shortest circuit must visit all edges exactly twice. You could prove this by induction. So let's consider the Open Loop TSP, in which the salesman is not required to return to the source. 

In this problem, your task is the Open Loop TSP on trees, i.e., finding the shortest distance traversing all nodes in a tree from any source without returning to the source.

Input

There's an interger \(n\) in the first line, indicating the number of nodes in the tree.

The next \(n-1\) lines consist of three integers \(a_i,b_i,w_i\) representing that there's an bidirected edge between \(a_i\) and \(b_i\) weighing \(w_i<2^{31}\).

For \(50\%\) of the testcases, \(n\leq5\times10^4\). For the other \(50\%\) of the testcases, \(n\leq10^6\).

Output

Please print the shortest distance traversing all nodes in a tree from any source without returning to the source.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Mr. Kuo is an adventurer. One day, he finds another secret room in a cave.

There is some hint to the password of this room.

 

Mr. Kuo is given a string S = s₁s₂...s_N consisting of L,  R, l, and r.

At first, Mr. Kuo has a string A = "0", a number x = 1, and the cursor is on 0.

For each letter c in S:

• If c is L, insert x to the left of the cursor, set cursor on x, and set x to x + 1.
• If c is R, insert x to the right of the cursor, set cursor on x, and set x to x + 1.
• If c is l, move the cursor to the far left.
• If c is r, move the cursor to the far right.

 

The final contents of A is the password. Please help Mr. Kuo find the password.

 

For example, S = "rRlL", then：

• s₁ = r, move the cursor to the far right(0), x = 1, A = "0", cursor on 0
• s₂ = R, insert x(=1) to the right of the cursor(0), x = 2, A = "01", cursor on 1
• s3 = l, move the cursor to the far left(0), x = 2, A = "01", cursor on 0
• s4 = L, insert x(=2) to the left of the cursor(0), x = 3, A = "201", cursor on 2

 

This problem is partial judge, you have to finish the four functions:

• addleft(int k): insert k to the left of the cursor
• addright(int k): insert k to the right of the cursor
• toleft(): move the cursor to the far left
• toright(): move the cursor to the far right

(Don't forget to include "function.h" in you code!)

Input

The first contains an integer T -- the number of testcases.

Each of the following line contains a string S.

For testcase 1~3, 1 <= T <= 100, length of S <= 2e5, S contains only L and R.

For testcase 4~6, 1 <= T <= 10, length of S <= 1000, S contains L,  R, l, and r.

For testcase 7~9, 1 <= T <= 100, length of S <= 2e5, S contains L,  R, l, and r.

Output

For each test case print a string A — the final contents of the password, seperated by spaces.

Sample Input  Download

Sample Output  Download

Partial Judge Code

13860.cpp

Partial Judge Header

13860.h

Tags

Discuss

Description

1. Only C and C++ are allowed. Solving problems with other languages (e.g. python, java) are forbidden, otherwise you'll get zero point.

2. Paper references, electronic devices, or other items that may contain any information relative to this exam are not allowed.

3. Before leaving, please tell TAs, we'll check if your accepted / partially accepted submissions are all written in C  or C++. After you pass the check, you may sign your name as a record and leave.

4. The score of each problem is shown below:

   • 13858: 40 points

   • 13860: 30 points

   • 13839: 30 points

If you get partially correct in a problem, your score of the problem will be

• score of the problem * number of testcases you passed / number of testcases

For example, if score of a problem is 10 points and the problem contains 6 testcases. If you pass the 3 testcases, you'll get 10*3/6=5 points on this problem.

Recommend order: 13839 -> 13860 -> 13858

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss