Maximizing Valid Parentheses Paths in a Tree

You are given a tree with n nodes. The 1^st node is pre-filled with a left parenthesis (. For every other node, you need to assign either ( or ) such that the number of valid parentheses paths in the tree is maximized. A path in the tree is considered a valid parentheses path if the string formed by the brackets along the path is a correct parentheses sequence. In a correct parentheses sequence, when read from left to right:

• The total number of ( equals the total number of ).
• At every prefix of the sequence, the number of ( is not less than the number of ).

It is guaranteed that there is a unique optimal assignment that maximizes the number of valid parentheses paths.

Note: In this problem, you are given the tree in an arbitrary order. You should compute an assignment for each vertex such that the overall count of valid parentheses paths in the tree is maximized.

Hint: Consider the parity of the distance from the fixed node (node 1) when assigning brackets.

The mathematical formulation can be summarized as: Let d(i) be the distance from node 1 to node i. Then, assign

[ \text{bracket}(i)= \begin{cases} ( & \text{if } d(i) \equiv 0 \pmod{2},\ ) & \text{if } d(i) \equiv 1 \pmod{2}. \end{cases} ]

Your output should be a string of n characters representing the bracket assignment for nodes 1 through n in order.

inputFormat

The first line contains an integer n (the number of nodes in the tree).

The following n-1 lines each contain two integers u and v indicating that there is an edge between nodes u and v in the tree.

It is guaranteed that the tree is connected and node 1 always has the left parenthesis pre-assigned.

outputFormat

Output a single line containing a string of n characters. The i^th character represents the bracket assigned to node i. The solution must maximize the number of valid parentheses paths in the tree (and the optimal assignment is unique).

sample

3
1 2
1 3

() )