La central eléctrica JOI tiene $N$ bases numeradas de $1$ a $N$. Las bases están conectadas por $N-1$ cables. El cable $i$ ($1 \le i \le N-1$) conecta la base $A_i$ y la base $B_i$ en ambas direcciones. Se puede ir de cualquier base a cualquier otra recorriendo algunos cables.

Cada base de la central eléctrica JOI tiene como máximo un generador. Cada generador tiene un interruptor. Al principio, todos los interruptores están apagados. Tú eres el director de la central eléctrica JOI. Puedes elegir algunos generadores y encender sus interruptores. (Se permite no elegir ninguno). Los generadores tienen las siguientes propiedades.

• Supongamos que las bases $x,y,z$ tienen generadores. Supongamos, además, que se puede ir de la base $x$ a la base $y$ y de la base $y$ a la base $z$, en ese orden, sin recorrer el mismo cable dos veces. Si los interruptores de los generadores de las bases $x$ y $z$ están encendidos, el generador de la base $y$ se avería.
• Un generador se activa si su interruptor está encendido y no está averiado.

Finalmente, recibirás recompensas por los generadores activados. Recibirás 1 yen por cada generador activado. Sin embargo, también tendrás que pagar los gastos de reparación de los generadores averiados. Pagarás 1 yen por cada generador averiado. Tu beneficio será el importe total de las recompensas menos el importe total de los gastos de reparación.

Escribe un programa que, dada la disposición de las bases y los cables y la información de los generadores, calcule tu beneficio máximo.

Entrada

Lee los siguientes datos de la entrada estándar.

$$ \begin{array}{l} N\\ A_1\ B_1\\ \vdots\\ A_{N-1}\ B_{N-1}\\ S \end{array} $$

Aquí, $S$ es una cadena de longitud $N$ que representa los generadores de las bases. Cada carácter de $S$ es 0 o 1. El carácter $i$ ($1 \le i \le N$) describe el generador de la base $i$. Es 0 si no hay un generador en la base $i$, y es 1 si la base $i$ tiene un generador.

Salida

Escribe una línea en la salida estándar. Debe contener tu beneficio máximo al elegir algunos generadores y encender todos los interruptores de los generadores elegidos.

Restricciones

• $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$).
• Se puede ir de cualquier base a cualquier otra recorriendo algunos cables.
• $S$ es una cadena de longitud $N$ formada por 0 y 1.
• $S$ contiene al menos un 1.

Subtareas

1. (6 puntos) $N \le 16$.
2. (41 puntos) $N \le 2\,000$.
3. (53 puntos) Sin restricciones adicionales.

Ejemplos

Entrada 1

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

Salida 1

3

Nota

En este ejemplo, las bases $1,2,5,6$ tienen generadores.

Si enciendes los interruptores de las bases $1,2,5$, los generadores de las bases $1,2,5$ se activarán y recibirás 3 yenes. Como no pagarás gastos de reparación, tu beneficio será de 3 yenes. Dado que este es tu beneficio máximo, la salida es $3$.

Por otro lado, si enciendes los interruptores de las bases $1,5,6$, el generador de la base $2$ se averiará y los generadores de las bases $1,5,6$ se activarán. Recibirás 3 yenes y pagarás 1 yen en gastos de reparación. Por tanto, tu beneficio será de 2 yenes.

Si enciendes los interruptores de las bases $1,2,5,6$, el generador de la base $2$ se averiará y los generadores de las bases $1,5,6$ se activarán. Recibirás 3 yenes y pagarás 1 yen en gastos de reparación. Por tanto, tu beneficio será de 2 yenes.

Entrada 2

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

Salida 2

3

Entrada 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

Salida 3

5