Balanced Trees

Farmer John's farm has the shape of a giant tree of $N$ pastures ($1 \le N \le 40{,}000$). Every pasture is labeled with either ( or ). Because the farm is a tree, there is exactly one simple path between any pair of pastures.

Reading the labels along a path, in a chosen direction, spells a string of parentheses. Some of these strings are balanced. Among all balanced strings that can be read off paths of the tree, Farmer John wants the largest possible nesting depth.

The nesting depth of a balanced parenthesis string is the maximum, over all of its prefixes, of the number of ( minus the number of ) in that prefix. For example, ()()() has nesting depth $1$, while ((()))() has nesting depth $3$. Writing the running excess of ( under each character makes this clear:

((()))()
12321010

Here is an example farm, each pasture drawn with its label:

'('--'('--')'--'('--')'
 |         |
')'       ')'--'('--'(' 
 |              |
')'            '('--')'--')'--')'--'('

Because a path is read in one direction, the same two pastures traversed the other way spell the reversed string (for instance () versus )(); both directions are allowed.

For the farm above, the deepest balanced string is ((())), with nesting depth $3$, obtained by walking from A to B:

'('--'('--')'--'('--')'
 |         |
')'       ')'--'('--'(' < A
 |              |
')'            '('--')'--')'--')'--'('
 ^C                            ^B

Note that this is different from the longest balanced string; for example (())(()), from A to C, has length $8$ but a smaller nesting depth.

Output the nesting depth of the deepest balanced path in the tree. If no path spells a balanced string, output $0$.

• Line $1$: a single integer $N$, the number of nodes in the tree.
• Lines $2 \ldots N$: line $i + 1$ contains a single integer $p_{i+1}$ with $1 \le p_{i+1} \le i$, denoting an edge between node $i + 1$ and node $p_{i+1}$.
• Lines $N + 1 \ldots 2N$: line $N + i$ contains either ( or ), the label of node $i$.

• A single integer: the maximum nesting depth among all balanced paths of the tree, or $0$ if no balanced path exists.

This is the farm from the problem statement, with node numbers shown below:

1'('--4'('--6')'--7'('--8')'
  |     |
2')'  5')'--9'('--10'('
  |           |
3')'       11'('--12')'--13')'--14')'--15'('

The deepest balanced path is $10 \to 9 \to 11 \to 12 \to 13 \to 14$, which spells ((())) and has nesting depth $3$.