Bị cuốn hút bởi những trải nghiệm với dấu ngoặc cân bằng cho đến nay, Farmer John muốn nhờ bạn giúp ông giải một bài toán cuối cùng. Trang trại của FJ có dạng một cây khổng lồ gồm \(N\) đồng cỏ (\(1 \le N \le 40\,000\)), mỗi đồng cỏ được ông gắn nhãn ( hoặc ). Ví dụ:

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

Nhớ rằng vì trang trại của ông là một cây, điều này có nghĩa là một số cặp đồng cỏ được nối với nhau bằng các hành lang sao cho tồn tại đúng một đường đi giữa hai đồng cỏ bất kỳ. FJ tin rằng một số đường đi này biểu diễn các chuỗi dấu ngoặc cân bằng. Cụ thể, trong tất cả những chuỗi cân bằng được biểu diễn bởi các đường đi trên cây, ông muốn biết độ sâu lồng nhau lớn nhất có thể tìm thấy. Độ sâu lồng nhau của một chuỗi dấu ngoặc cân bằng là giá trị lớn nhất, xét trên mọi tiền tố của chuỗi, của số dấu ( dư ra trong tiền tố đó. Ví dụ, chuỗi ()()() có độ sâu lồng nhau bằng 1, nhưng chuỗi ((()))() có độ sâu lồng nhau bằng 3, như có thể thấy rõ khi ta đếm số dấu ( dư ra ở mỗi tiền tố của chuỗi:

((()))()
12321010

Trong trang trại ví dụ ở trên, chuỗi sâu nhất là ((())) với độ sâu 3 và có thể thu được bằng cách đi theo đường từ A đến B dưới đây:

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

Lưu ý rằng điều này khác với chuỗi cân bằng dài nhất; chẳng hạn, (())(()), bắt đầu tại A và kết thúc tại C, có độ dài 8.

Nhiệm vụ của bạn là in ra độ sâu lồng nhau của đường đi cân bằng sâu nhất trên cây.

Dữ liệu vào

• Dòng 1 chứa một số nguyên duy nhất \(N\), là số đỉnh của cây.
• Các dòng \(2..N\): dòng \(i+1\) chứa một số nguyên duy nhất \(p_{i+1}\) (\(1 \le p_{i+1} \le i\)), biểu thị một cạnh nối đỉnh \(i+1\) với đỉnh \(p_{i+1}\) trên cây.
• Các dòng \(N+1..2N\): dòng \(N+i\) chứa ( hoặc ), là nhãn của đỉnh \(i\).

Dữ liệu ra

• Dòng 1 chứa một số nguyên duy nhất là độ sâu lồng nhau lớn nhất của một đường đi cân bằng.

Ví dụ

15
1
2
1
4
4
6
7
5
9
9
11
12
13
14
(
)
)
(
)
)
(
)
(
(
(
)
)
)
(

3

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

Nguồn

USACO 2012 November Contest, Gold — Problem 3: Balanced Trees

Tác giả đề: Brian Dean, 2012.