The JOI power plant has ~N~ bases numbered from ~1~ to ~N~. The bases are connected by ~N-1~ wires. The ~i~-th wire ~(1 \le i \le N-1)~ connects the base ~A_i~ and the base ~B_i~, in both directions. We can travel from any base to any other base by passing through some wires.

Each base of the JOI power plant has at most one power generator. Each power generator has a switch. In the beginning, the switch of every power generator is OFF. You are the director of the JOI power plant. You may choose some power generators, and turn the switches of the chosen power generators to ON. (It is allowed to choose nothing.) The power generators have the following properties.

• Assume that the bases ~x, y, z~ have power generators. Moreover, assume that we can travel from the base ~x~ to the base ~y~ and from the base ~y~ to the base ~z~, in this order, so that we do not pass through the same wire twice. If the switches of the power generators of the base ~x~ and the base ~z~ are ON, then the power generator of the base ~y~ is broken.
• A power generator will be activated if its switch is ON and it is not broken.

Finally, you will get rewards from activated power generators. You will get ~1~ yen for each activated power generator. However, you will also have to pay repair expenses for broken power generators. You will have to pay ~1~ yen for each broken power generator. The total amount of rewards minus the total amount of repair expenses will be your profit.

Write a program which, given the arrangement of the bases and the wires, and the information of power generators, calculates the maximum of your profit.

Input Specification

Read the following data from the standard input.

~N~

~A_1\ B_1~

~\vdots~

~A_{N-1}\ B_{N-1}~

~S~

Here ~S~ is a string of length ~N~ representing the power generators of the bases. Each character of ~S~ is either 0 or 1. The ~i~-th character ~(1 \le i \le N)~ describes the power generator of the base ~i~. It is 0 if there is no power generator in the base ~i~. It is 1 if the base ~i~ has a power generator.

Output Specification

Write one line to the standard output. The output should contain the maximum of your profit when you choose some power generators, and turn all the switches of the chosen power generators to ON.

Constraints

• ~1 \le N \le 200\,000~.
• ~1 \le A_i \le N~ ~(1 \le i \le N-1)~.
• ~1 \le B_i \le N~ ~(1 \le i \le N-1)~.
• ~A_i \ne B_i~ ~(1 \le i \le N-1)~.
• We can travel from any base to any other base by passing through some wires.
• ~S~ is a string of length ~N~ consisting of 0, 1.
• ~S~ contains at least one 1.

Subtasks

1. (6 points) ~N \le 16~.
2. (41 points) ~N \le 2\,000~.
3. (53 points) No additional constraints.

Sample Input 1

6
2 3
4 3
1 3
3 5
6 2
110011

Sample Output 1

3

Explanation for Sample 1

In this sample input, the bases ~1, 2, 5, 6~ have power generators.

If you turn the switches of the bases ~1, 2, 5~ to ON, the power generators of the bases ~1, 2, 5~ will be activated, and you get ~3~ yen. Since you will not pay repair expenses, your profit is ~3~ yen. Since it is the maximum of your profit, output ~3~.

On the other hand, if you turn the switches of the bases ~1, 5, 6~ to ON, the power generator of the base ~2~ will be broken, and the power generator of the bases ~1, 5, 6~ will be activated. You will get ~3~ yen, and you will pay ~1~ yen for repair expenses. Therefore, your profit will be ~2~ yen.

If you turn the switches of the bases ~1, 2, 5, 6~ to ON, the power generator of the base ~2~ will be broken, and the power generator of the bases ~1, 5, 6~ will be activated. You will get ~3~ yen, and pay ~1~ yen for repair expenses. Therefore, your profit will be ~2~ yen.

Sample Input 2

8
1 2
3 5
6 4
4 5
5 2
7 2
2 8
11111111

Sample Output 2

3

Sample Input 3

16
7 10
5 11
9 4
14 12
2 11
14 16
4 2
1 13
11 3
7 1
15 9
2 1
11 6
14 9
8 9
0111111001001110

Sample Output 3

5