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

10966.c

Partial Judge Header

10966.h

Tags

Discuss

Description

Given an prefix Boolean expression, which has at most 4 variables ‘A’, ’B’, ‘C’, and ‘D’, and two operators ‘&’ and ‘|’. Output its infix presentation with necessary parenthesis.

• Ex: input: ||A&BCD
  output: A|(B&C)|D

Hint : About necessary parenthesis, you can observe the syntax tree which has been constructed, then you will find out the rule. For example, the infix expression of |&|AB&CDA with necessary parenthesis is A|B&(C&D)|A, rather than (A|B)&(C&D)|A .

• Syntax tree of |&|AB&CDA

You will be provided with main.c and function.h, and asked to implement function.c.

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 first line will have a number N with the number of test cases, followed by N lines of input, each contain the prefix Boolean expression.

Output

There are N lines infix expression with necessary parenthesis.

Sample Input  Download

Sample Output  Download

Partial Judge Code

10968.c

Partial Judge Header

10968.h

Tags

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

Tags

Discuss

Description

Stiff Waist Beast is going on vacation. However, he thinks that planning the trip is too trivial. He has a lot of much important things to do. How can he waste time on it! So he decides to give this task to you. 

The city Stiff Waist Beast is going to travel to has N viewpoints. Interestingly, for every viewpoint a and b, there exist only one shortest path, which means the map of the city is a tree. Stiff Waist Beast wants to go to Q places, so you need to tell him how to get from his hotel to the places he wants to visit. Since Stiff Waist Beast doesn't like to go too far, so the length of every path is less than 1000.

 

Input

The first line contains two integers N and Q. The city has N viewpoints, the viewpoints are numbered from 0 to N - 1, and 0 is the hotel that Stiff Waist Beast lives in. 

The next N - 1 lines contain two integer v_i and u_i, there is a road between v_i and u_i.

The next line has Q integers a_i, means the places Stiff Waist Beast wants to visit.

2 <= N <= 2e5.

0 <= v_i and u_i <= N - 1.

1 <= a_i <= N - 1.

For testcase 1~3, 1 <= Q <= 500.

For testcase 4~6, 1 <= Q <= 2e4.

Output

For every a_i, tell Stiff Waist Beast how to get from his hotel to viewpoint a_i, that is, print the path from 0 to a_i.

Sample Input  Download

Sample Output  Download

Tags

Discuss