12821번 - Universities 다국어

You have just graduated from the high school and are looking for a university to enroll in. There are N magic universities in Bytelandia. Each university teaches either black magic or white magic. There are N − 1 bidirectional roads between the universities, each road connecting two different universities. Universities are connected in such a way, that there exists a unique path between any two universities.

You plan to visit some of the universities. Each university has a happiness factor, by which your overall happiness increases when you visit the university. Note that if the happiness factor is negative, your overall happiness decreases.

To plan your trip, you choose two different universities, the departure and the destination university. You will visit all the universities on the path between the departure and destination universities, both of them including. To keep things in balance, you must visit the same number of white magic universities as black magic universities.

You are now wondering, what is the optimal trip that maximizes the happiness of the trip, i.e. sum of the happiness factors of the universities you visit.

You are given the description of universities and connections between them. Find the optimal trip around the universities, in which you visit the same number of black and white magic universities and the happiness of the trip is as large as possible.

Input consists of four lines.

First line contains a single integer N (2 ≤ N ≤ 10⁵), number of universities (universities are numbered from 1 to N).

Second line contains a string of length N, consisting of “B” and “W” characters. If the i-th character is “B”, then the i-th university is teaching black magic. If the i-th character is “W”, then the i-th university is teaching white magic. There will be at least one university teaching white magic and at least one university teaching black magic.

Third line contains N space-separated integers h₁h₂ . . . h_N (−10⁵ ≤ h_i ≤ 10⁵). Integer h_i is the happiness factor of the i-th university.

Fourth line contains N − 1 space-separated integers v₁v₂ . . . v_N−1. Integer v_i means there is a road connecting the universities with numbers v_i and (i + 1) (1 ≤ v_i ≤ i).

Output exactly one integer, maximum overall happiness of the trip, in which you visit the same number of black and white magic universities.