La centrale électrique de JOI comporte $N$ sites numérotés de $1$ à $N$. Ces sites sont reliés par $N-1$ câbles. Le $i$-ème câble ($1 \le i \le N-1$) relie les sites $A_i$ et $B_i$ dans les deux sens. Il est possible de se rendre de n'importe quel site à n'importe quel autre en empruntant des câbles.

Chaque site de la centrale électrique de JOI possède au plus un générateur. Chaque générateur est muni d'un interrupteur. Au départ, tous les interrupteurs sont en position arrêt. Vous êtes le directeur de la centrale électrique de JOI. Vous pouvez choisir certains générateurs et mettre leurs interrupteurs en position marche. (Il est permis de n'en choisir aucun.) Les générateurs ont les propriétés suivantes.

• Supposons que les sites $x,y,z$ possèdent des générateurs. Supposons également qu'il soit possible de se rendre du site $x$ au site $y$, puis du site $y$ au site $z$, dans cet ordre, sans emprunter deux fois le même câble. Si les interrupteurs des générateurs des sites $x$ et $z$ sont en position marche, alors le générateur du site $y$ tombe en panne.
• Un générateur est actif si son interrupteur est en position marche et s'il n'est pas en panne.

À la fin, vous recevez des récompenses pour les générateurs actifs. Vous recevez 1 yen par générateur actif. Toutefois, vous devez également payer les frais de réparation des générateurs en panne : 1 yen par générateur en panne. Votre bénéfice est le montant total des récompenses moins le montant total des frais de réparation.

Écrivez un programme qui, étant donnés la disposition des sites et des câbles ainsi que les renseignements sur les générateurs, calcule votre bénéfice maximal.

Entrée

Lisez les données suivantes sur l'entrée standard.

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

Ici, $S$ est une chaîne de longueur $N$ représentant les générateurs des sites. Chaque caractère de $S$ est 0 ou 1. Le $i$-ème caractère ($1 \le i \le N$) décrit le générateur du site $i$. Il vaut 0 si le site $i$ ne possède pas de générateur, et 1 si le site $i$ en possède un.

Sortie

Écrivez une ligne sur la sortie standard. Elle doit contenir votre bénéfice maximal lorsque vous choisissez certains générateurs et mettez tous leurs interrupteurs en position marche.

Contraintes

• $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$).
• Il est possible de se rendre de n'importe quel site à n'importe quel autre en empruntant des câbles.
• $S$ est une chaîne de longueur $N$ constituée de 0 et de 1.
• $S$ contient au moins un 1.

Sous-tâches

1. (6 points) $N \le 16$.
2. (41 points) $N \le 2\,000$.
3. (53 points) Aucune contrainte supplémentaire.

Exemples

Entrée 1

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

Sortie 1

3

Remarque

Dans cet exemple, les sites $1,2,5,6$ possèdent des générateurs.

Si vous mettez les interrupteurs des sites $1,2,5$ en position marche, les générateurs de ces sites sont actifs, et vous recevez 3 yens. Comme vous n'avez aucun frais de réparation à payer, votre bénéfice est de 3 yens. Ce bénéfice étant maximal, affichez $3$.

En revanche, si vous mettez les interrupteurs des sites $1,5,6$ en position marche, le générateur du site $2$ tombe en panne, et les générateurs des sites $1,5,6$ sont actifs. Vous recevez 3 yens et payez 1 yen de frais de réparation. Votre bénéfice est donc de 2 yens.

Si vous mettez les interrupteurs des sites $1,2,5,6$ en position marche, le générateur du site $2$ tombe en panne, et les générateurs des sites $1,5,6$ sont actifs. Vous recevez 3 yens et payez 1 yen de frais de réparation. Votre bénéfice est donc de 2 yens.

Entrée 2

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

Sortie 2

3

Entrée 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

Sortie 3

5