Background

Memory Forest.

The mystery of the beginning, someday.

Tell it to the unknown end of this.

— Eguchi Takahiro, “Beside You”.

Problem Description

I believe that everyone who has read this part of the story does not want others to suffer the same pain, but Taniel can still only disappear, right?

Taniel finally left behind a rooted tree with root $1$. On each node of the tree, there is a memory fragment. Some fragments represent the beginning of a world’s memory, while other fragments represent the end of a world’s memory.

At this time, a butterfly モリモリあつし flew to the tree. During its flight on the tree, the butterfly passed through some nodes. Alice can be sure that the number of nodes the butterfly passed through is at least $2$, but she forgot the exact number.

Alice found that all nodes the butterfly passed through are connected to each other. When she looked at every simple path (for each connected block with more than $1$ node) from the shallowest node in the connected block to any leaf node of the connected block (a node is a leaf node of the connected block if and only if it has no child nodes in the tree, or none of its child nodes in the tree belongs to the connected block), she found that the memories on these paths are complete. Alice considers the memory on a path to be complete if and only if, on this path, there is neither a case where a world’s memory ends before it starts (a fragment indicating the end of a memory appears when there is no unfinished memory in the middle of the path), nor a case where a world’s memory starts but has no end (there are still unfinished memories after the path ends).

Unfortunately, she has already forgotten which nodes the butterfly passed through, so you need to tell her the maximum possible number of nodes the butterfly could have passed through.

Formal statement

Given a rooted tree $T=(V,E)$ with $n$ nodes rooted at $1$, each node has a value $c_i$ which is either a left parenthesis or a right parenthesis, and nodes are numbered $1$ to $n$.

We define a node set $V'\subseteq V$ to be valid if and only if $|V'|>1$ (i.e. the size of $V'$ is greater than $1$) and for all $u,v \in V'$, the simple path from $u$ to $v$ passes only through nodes in $V'$.

We also define $E'\subseteq E$ as the edge set with the minimum size such that for all $u,v \in V'$, the simple path from $u$ to $v$ passes only through edges in $E'$.

Define the root of a valid node set $V'$ as the node in $V'$ with the minimum depth.

Define $u$ to be a leaf node of a valid node set $V'$ if and only if $u$ is not the root of $V'$, and the number of nodes $v$ satisfying $v \in V', (u,v) \in E'$ is $1$.

Find a valid node set $S$ such that on the path from its root to any of its leaves, the node values along the path, concatenated in order, form a valid parenthesis sequence, and maximize $|S|$.

We define a valid parenthesis sequence by the following rules:

• The empty string (i.e. a string of length $0$) is a valid parenthesis sequence.

• If strings $\text{A,B}$ are both valid parenthesis sequences, then the string $\text{AB}$ (i.e. concatenating $\text{A}$ and $\text{B}$ in order) is also a valid parenthesis sequence.

• If string $\text{A}$ is a valid parenthesis sequence, then the string $\text{(A)}$ is a valid parenthesis sequence.

You need to output the maximum $|S|$ that satisfies the requirements.

Input Format

The first line contains a positive integer $n$, the number of nodes in the tree.

The second line contains a string $c$ of length $n$. $c_i$ is ( meaning this node has a fragment marking the start of a memory, and $c_i$ is ) meaning this node has a fragment marking the end of a memory.

The next $n-1$ lines each contain two positive integers $u, v$, indicating that there is an edge between nodes $u$ and $v$.

Output Format

Output one line with one integer, the answer.

3
())
1 2
1 3

3

8
()))())(
1 2
1 3
3 4
3 5
3 6
5 7
2 8

5

Hint

Sample explanation

The maximum valid node set $S$ that the butterfly can pass through is $\{1,2,3\}$.

The maximum valid node set $S$ that the butterfly can pass through is $\{1,2,3,5,7\}$.

Constraints

This problem uses bundled testdata.

Special property $\text{A}$: it is guaranteed that the tree degenerates into a chain (not necessarily with node $1$ as an endpoint).

Special property $\text{B}$: it is guaranteed that on any path from any node to a leaf in the original tree, the number of right parentheses is not less than the number of left parentheses.

For all data, $1\le n\le 5\times 10^5$, $1\le u,v \le n$, and $c_i$ is either ( or ).

Translated by ChatGPT 5