Pembangkit listrik JOI memiliki $N$ pos yang diberi nomor dari $1$ hingga $N$. Pos-pos tersebut dihubungkan oleh $N-1$ kabel. Kabel ke-$i$ ($1\le i\le N-1$) menghubungkan pos $A_i$ dan pos $B_i$ dalam kedua arah. Kita dapat berpindah dari pos mana pun ke pos lainnya dengan melewati beberapa kabel.

Setiap pos di pembangkit listrik JOI memiliki paling banyak satu generator listrik. Setiap generator memiliki sakelar. Awalnya, semua sakelar generator dalam keadaan MATI. Anda adalah direktur pembangkit listrik JOI. Anda boleh memilih beberapa generator dan mengubah sakelar generator yang dipilih menjadi HIDUP. (Anda juga boleh tidak memilih apa pun.) Generator-generator tersebut memiliki sifat berikut.

• Misalkan pos $x,y,z$ memiliki generator. Selain itu, misalkan kita dapat berpindah dari pos $x$ ke pos $y$, lalu dari pos $y$ ke pos $z$, dalam urutan tersebut, tanpa melewati kabel yang sama dua kali. Jika sakelar generator di pos $x$ dan pos $z$ HIDUP, maka generator di pos $y$ rusak.
• Sebuah generator akan aktif jika sakelarnya HIDUP dan generator tersebut tidak rusak.

Pada akhirnya, Anda menerima imbalan dari generator yang aktif. Anda mendapatkan 1 yen untuk setiap generator yang aktif. Namun, Anda juga harus membayar biaya perbaikan untuk generator yang rusak. Anda harus membayar 1 yen untuk setiap generator yang rusak. Jumlah imbalan dikurangi jumlah biaya perbaikan merupakan keuntungan Anda.

Tulislah program yang, diberikan susunan pos dan kabel serta informasi generator, menghitung keuntungan maksimum Anda.

Masukan

Baca data berikut dari masukan standar.

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

Di sini, $S$ adalah string sepanjang $N$ yang menyatakan generator pada setiap pos. Setiap karakter $S$ adalah 0 atau 1. Karakter ke-$i$ ($1\le i\le N$) menggambarkan generator di pos $i$. Karakter tersebut adalah 0 jika pos $i$ tidak memiliki generator, dan 1 jika pos $i$ memiliki generator.

Keluaran

Tuliskan satu baris ke keluaran standar. Keluaran harus berisi keuntungan maksimum Anda ketika Anda memilih beberapa generator dan mengubah semua sakelar generator yang dipilih menjadi HIDUP.

Batasan

• $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$).
• Kita dapat berpindah dari pos mana pun ke pos lainnya dengan melewati beberapa kabel.
• $S$ adalah string sepanjang $N$ yang terdiri dari 0 dan 1.
• $S$ mengandung setidaknya satu 1.

Subsoal

1. (6 poin) $N\le 16$.
2. (41 poin) $N\le 2\,000$.
3. (53 poin) Tidak ada batasan tambahan.

Contoh

Masukan 1

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

Keluaran 1

3

Penjelasan

Dalam contoh ini, pos $1,2,5,6$ memiliki generator.

Jika Anda mengubah sakelar di pos $1,2,5$ menjadi HIDUP, generator di pos $1,2,5$ akan aktif, dan Anda mendapat 3 yen. Karena Anda tidak membayar biaya perbaikan, keuntungan Anda adalah 3 yen. Karena ini merupakan keuntungan maksimum, keluarkan $3$.

Sebaliknya, jika Anda mengubah sakelar di pos $1,5,6$ menjadi HIDUP, generator di pos $2$ akan rusak, dan generator di pos $1,5,6$ akan aktif. Anda mendapat 3 yen dan membayar biaya perbaikan 1 yen. Jadi, keuntungan Anda adalah 2 yen.

Jika Anda mengubah sakelar di pos $1,2,5,6$ menjadi HIDUP, generator di pos $2$ akan rusak, dan generator di pos $1,5,6$ akan aktif. Anda mendapat 3 yen dan membayar biaya perbaikan 1 yen. Jadi, keuntungan Anda adalah 2 yen.

Masukan 2

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

Keluaran 2

3

Masukan 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

Keluaran 3

5