Description

Given an infix Boolean expression with parentheses, which has at most 4 variables ‘A’, ’B’, ‘C’, and ‘D’, and two operators ‘&’ and ‘|’. Build a corresponding syntax tree for it.

To parse the infix expression with parentheses, use the grammar below.

EXPR = FACTOR | EXPR OP FACTOR

FACTOR = ID | (EXPR)

EXPR is the expression, ID is one of ‘A’, ‘B’, ’C’, or ‘D’, and OP is one of ‘&’ or ‘|’.

You will be provided with main.c and function.h. main.c contains the implementation of functions printPrefix and freeTree. function.h contains the definition of tree node and variables. You only need to implement the following three functions in function.c.

BTNode* makeNode(char c)   // create a node without any child

BTNode* EXPR()   // parse an infix expression and generate a syntax tree

BTNode* FACTOR()   // use the parse grammar FACTOR = ID | (EXPR) to deal with parentheses

For OJ submission:

        Step 1. Submit only your function.c into the submission block.(Please choose C compiler)

        Step 2. Check the results and debug your program if necessary.

Input

The input contains N infix expressions, which has at most 4 variables ‘A’, ’B’, ‘C’, and ‘D’, two operators ‘&’ and ‘|’, and parentheses. All parentheses are matched. 

Output

The output contains N prefix expressions without parentheses, which are preorders of syntax trees.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Discuss

Description

Mr. Kuo is an adventurer. One day, he finds a special "tree".

The tree consists of N vertices. 

There are exactly one simple path between any two vertices.

Mr. Kuo wants to do the following operation K times to this tree：

• If the tree is empty, do nothing.
• If the tree consists of one vertex, remove this vertex.
• If the tree consists of two vertices, remove both vertices.
• Otherwise, remove all the leaf of the tree.

（A leaf of a tree is a vertex that is connected to at most one vertex.）

Mr. Kuo is wondering how many vertices will remain after he performs the operations K times.

Take the sample test as the example：

• In test case 1, {2, 4, 5, 7, 9, 12, 13} are removed and {1, 3, 6, 8, 10, 11} remain.
• In test case 2, {1, 2} are removed and no vertex remains.
• In test case 3, {1, 2, 6, 7} are removed and {3, 4, 5} remain.
• In test case 4, {2, 4, 5} are removed and {1, 3, 6} remain.
• In test case 5, no vertices are removed and {1, 2, 3} remain.

The picture below is the tree of the test case 4 in the sample test.

The picture below is the tree after Mr. Kuo performs the operation once.

Input

The first line contains one integer T — the number of test cases. Description of the test cases follows.

The first line of each test cases contains two integer N K — the number of vertices in the tree and the number of operations Mr. Kuo performs.

Each of the next N - 1 lines contains two integers u_i and v_i — there is an edge between u_i and v_i.

For each test：

1. T ≤ 100, N ≤ 20
2. T ≤ 100, N ≤ 100
3. T ≤ 100, N ≤ 500
4. T ≤ 100, N ≤ 1000
5. T ≤ 100, N ≤ 5000
6. T ≤ 100, N ≤ 20000

1 ≤ u_i, v_i ≤ N

0 ≤ K ≤ N for all test.

Output

For each test case print an integer — the number of verticees remain in the tree.

Sample Input  Download

Sample Output  Download

Discuss

Description

"Run?"
"Who's running?"
"Running where?"
"And why?!" said Shadow sama. At the same time, Shadow sama spreads his mana all over Midgar Kingdom.

"Observe!"
"And witness for yourselves!"
"Supremely ultimate, almighty and unparalleled attack!"
"I..."
"...am..."

Beta (one of the Seven Shadows, higher-ups of Shadow Garden), who is keen on writing down feats of Shadow sama, is stunned by the sight of Shadow Sama's attack, and missed the chance to record it.

Beta has the map of Midgar Kingdom, which is a tree with \(N\) nodes, numbered from \(1\) to \(N\). Shadow Sama is at one of the nodes as he spreads his mana. With \(k\) unit of mana, Shadow Sama can cover the node he is at, and all the nodes that are at most \(k\) edges away from him.

Beta knows that Shadow Sama is so smart that he must have chosen the place he was at wisely, and spent the least amount of mana to cover the whole Midgar Kingdom. Sasuga Shadow Sama!

However, since Shadow Sama's attack is so breathtaking, Beta forgot to record the details of it. In order to demonstrate Shadow Sama's wisdom, you need to calculate the minimum amount of mana required for him to cover the whole Midgar Kingdom.

For the sample test case, we can draw the tree as shown below. When Shadow Sama is at node #1 (or node #5), he can cover all the nodes with 3 units of mana.

Input

The first line contains an integer \(N\), the number of nodes in the tree.

For the following \(N-1\) lines, each line contains two integers \(u_i\) and \(v_i\), indicating that there is an bidirectional edge between node \(u_i\) and node \(v_i\).

\(N\)
\(u_1 \quad v_1\)
\(u_2 \quad v_2\)
\(\vdots\)
\(u_{N-1} \quad v_{N-1}\)

Constraints

• \(1 \leq N \leq 10^5\)
• \(1 \leq u_i, v_i \leq N\)
• The input is a tree.

Output

Output contains one line with an integer, the minimum units of mana required to cover the whole Midgar Kingdom.

You don't have to print spaces or newlines at the end of the line.

Sample Input  Download

Sample Output  Download

Discuss

Description

TAs want to schedule a physical meeting but are too lazy to think about where they want to meet. Since they are lazy and don't want to move too much, please help them find out the optimal meeting location that minimizes the total distance they need to travel.

The distance is calculated using Manhattan Distance, following is how the distance is calculated:

$$\begin{aligned} &p_1 = (x_1, y_1) \\ &p_2 = (x_2, y_2) \\ &\text{distance}(p_1, p_2) = |x_1 - x_2| + |y_1 - y_2| \end{aligned}$$

• Hint 1: It is somehow related to quick sort
• Hint 2: Is it possible to not sort the entire array

Input

The first line contains one integer $N$, representing the number of TA.

The next $N$ lines each contains two integers, $x_i$ and $y_i$, representing the $x$ and $y$ coordinate of each TA respectively.

Contraints

• $1 \leq N \leq 3 \times 10^6$
• $-10^9 \leq x_i , y_i \leq 10^9$

Subtask

1. (Testcases 1-4) $1 \leq N \leq 3000$
2. (Testcases 5-8) No additional constraints.

Output

Output the minimum total distance they need to travel.

Noted that you should output one single line.

Sample Input  Download

Sample Output  Download

Discuss

Description

You are given two rooted binary trees, $X$ and $Y$, in a special format, each with $N$ vertices, numbered from $0$ to $N-1$. The format is described by the following EBNF (Extended Backus–Naur form):

The tree $X$: TREE ::= '(' INT '/' TREE '/' TREE ')' | NIL
The tree $Y$: TREE ::= INT '(' TREE ')' '(' TREE ')' | NIL

It means that a tree is a integer followed by two subtrees or a NIL. The integer represents which vertex the root of the tree is. If the tree is a NIL, it means that the tree is empty.

Two binary trees are considered identical if and only if:

1. Both trees are empty (NIL), or
2. Both trees have roots, and:
   • Their root values are equal AND
   • Their left subtrees are identical AND
   • Their right subtrees are identical

Here is a example. In the following figure, tree (a) will be represented as (2/(1//)/(0//)) and 2(1()())(0()()),
tree (b) as (2/(0//)/(1//)) and 2(0()())(1()()), and they are NOT identical.

Input

Input contains three lines. The first line contains an integer $N$, the number of vertices in each tree.

For the following two lines, each line contains a string, representing tree $X$ and $Y$ respectively in the EBNF format.

Contraints

• $1 \leq N \leq 10^5$
• Length of $X$ and $Y$ won't exceed $10^6$
• $X$ only contain character '(', ')', '/' and digit.
• $Y$ only contain character '(', ')' and digit.

Output

If the two trees are identical, output "YES", otherwise output "NO" (without quote)

Noted that you should output one single line.

Sample Input  Download

Sample Output  Download

Discuss