Cây cân bằng

Cho cây $N$ nút, mỗi nút được gán nhãn ( hoặc ). Tìm độ lồng tối đa của bất kỳ đường đi trên cây nào tạo thành chuỗi ngoặc hợp lệ.

Độ lồng của chuỗi hợp lệ = giá trị lớn nhất của tổng tiền tố (với ( = +1, ) = -1).

Dữ liệu vào

• Dòng $1$: Số nguyên $N$.
• $N-1$ dòng tiếp: $p_{i+1}$ — cha của nút $i+1$.
• $N$ dòng tiếp: Nhãn của nút $1,2,\dots ,N$ (mỗi dòng một ký tự ( hoặc )).

Dữ liệu ra

Một số nguyên — độ lồng tối đa.

Ràng buộc

• $1\le N\le 40000$

Ví dụ