Maximum Valid Memory Subtree

You are given a rooted tree \(T=(V,E)\) with \(n\) nodes numbered from \(1\) to \(n\) where node \(1\) is the root. Each node \(i\) carries a character \(c_i\) which is either a left bracket \((\) or a right bracket \())\). A subset of nodes \(S\subseteq V\) is called legal if:

• \(|S|>1\) (i.e. it contains at least two nodes);
• For every pair of nodes \(u,v \in S\), the unique simple path between \(u\) and \(v\) in \(T\) lies entirely in \(S\).

For a legal set \(S\), define its root as the node with the minimum depth (the smallest distance to the tree root \(1\)). In the unique tree induced by \(S\) (i.e. with edge set \(E'\) consisting of the edges of \(T\) connecting nodes in \(S\) ), a node \(u\) (with \(u\neq \text{root}\)) is called a leaf if it has degree 1 in the induced tree.

We say that a path (represented by the sequence of nodes) is valid if, when concatenating the bracket characters along the path (in order from the root to a leaf), the resulting string forms a valid parentheses sequence. Here a valid parentheses sequence is defined by the rules:

• The empty string is valid.
• If \(A\) and \(B\) are valid, then the concatenation \(AB\) is valid.
• If \(A\) is valid, then \((A)\) is valid.

Your task is to find a legal subset \(S\) (i.e. a connected set of nodes in \(T\) with \(|S|>1\)) such that for every leaf \(u\) in the induced subtree (with the chosen root), the simple path from the root of \(S\) to \(u\) yields a valid parentheses sequence. Among all such legal subsets, output the maximum possible size \(|S|\). If no legal subset satisfies the condition, output 0.

Input/Output Format: See below.

inputFormat

The input is given as follows:

• The first line contains a single integer (n) denoting the number of nodes in the tree.
• The second line contains a string of length (n) consisting of characters '(' and ')', where the (i)th character denotes the bracket at node (i).
• Each of the next (n-1) lines contains two integers (u) and (v) denoting that there is an edge between nodes (u) and (v) in the tree.

outputFormat

Output a single integer, the maximum size of a legal subset (S) such that for every leaf in the induced subtree (from the legal subset’s root) the concatenation of node brackets forms a valid parentheses sequence. If no such subset exists, output 0.

sample

3
(()
1 2
2 3

2