تضم محطة كهرباء JOI عددًا قدره $N$ من القواعد، مرقمة من $1$ إلى $N$. تتصل القواعد بواسطة $N-1$ سلكًا. يربط السلك $i$ ($1 \le i \le N-1$) القاعدة $A_i$ بالقاعدة $B_i$ في كلا الاتجاهين. يمكن الانتقال من أي قاعدة إلى أي قاعدة أخرى عبر بعض الأسلاك.

تحتوي كل قاعدة في محطة كهرباء JOI على مولد كهربائي واحد على الأكثر. لكل مولد مفتاح. في البداية، تكون مفاتيح جميع المولدات في وضع الإيقاف. أنت مدير محطة كهرباء JOI. يمكنك اختيار بعض المولدات وتحويل مفاتيح المولدات المختارة إلى وضع التشغيل. (يسمح بعدم اختيار أي مولد.) تتمتع المولدات بالخصائص التالية.

• افترض أن القواعد $x,y,z$ تحتوي على مولدات. وافترض أيضًا أنه يمكن الانتقال من القاعدة $x$ إلى القاعدة $y$، ثم من القاعدة $y$ إلى القاعدة $z$ بهذا الترتيب، دون المرور بالسلك نفسه مرتين. إذا كان مفتاحا مولدي القاعدتين $x$ و$z$ في وضع التشغيل، فإن مولد القاعدة $y$ يتعطل.
• ينشط المولد إذا كان مفتاحه في وضع التشغيل ولم يكن معطلًا.

في النهاية، تحصل على مكافآت من المولدات النشطة. ستحصل على ين واحد مقابل كل مولد نشط. لكن عليك أيضًا دفع تكاليف إصلاح المولدات المعطلة، بمقدار ين واحد مقابل كل مولد معطل. ربحك هو مجموع المكافآت ناقص مجموع تكاليف الإصلاح.

اكتب برنامجًا يحسب أكبر ربح ممكن، عند إعطائه ترتيب القواعد والأسلاك ومعلومات المولدات.

الإدخال

اقرأ البيانات التالية من الإدخال القياسي.

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

هنا $S$ سلسلة طولها $N$ تصف المولدات في القواعد. كل محرف في $S$ هو 0 أو 1. يصف المحرف $i$ ($1 \le i \le N$) مولد القاعدة $i$. يكون 0 إذا لم يوجد مولد في القاعدة $i$، ويكون 1 إذا كانت القاعدة $i$ تحتوي على مولد.

الإخراج

اطبع سطرًا واحدًا في الإخراج القياسي. يجب أن يحتوي على أكبر ربح ممكن عند اختيار بعض المولدات وتحويل جميع مفاتيح المولدات المختارة إلى وضع التشغيل.

القيود

• $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$).
• يمكن الانتقال من أي قاعدة إلى أي قاعدة أخرى عبر بعض الأسلاك.
• $S$ سلسلة طولها $N$ تتكون من 0 و1.
• تحتوي $S$ على محرف 1 واحد على الأقل.

المهام الفرعية

1. (6 نقاط) $N \le 16$.
2. (41 نقطة) $N \le 2\,000$.
3. (53 نقطة) لا توجد قيود إضافية.

أمثلة

الإدخال 1

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

الإخراج 1

3

ملاحظة

في هذا المثال، تحتوي القواعد $1,2,5,6$ على مولدات.

إذا حولت مفاتيح القواعد $1,2,5$ إلى وضع التشغيل، فستنشط مولدات القواعد $1,2,5$، وستحصل على $3$ ينات. ولأنك لن تدفع تكاليف إصلاح، فإن ربحك هو $3$ ينات. وهذا هو أكبر ربح ممكن، لذا اطبع $3$.

من ناحية أخرى، إذا حولت مفاتيح القواعد $1,5,6$ إلى وضع التشغيل، فسيتعطل مولد القاعدة $2$، وستنشط مولدات القواعد $1,5,6$. ستحصل على $3$ ينات وتدفع ينًا واحدًا للإصلاح، ولذلك سيكون ربحك $2$ ين.

إذا حولت مفاتيح القواعد $1,2,5,6$ إلى وضع التشغيل، فسيتعطل مولد القاعدة $2$، وستنشط مولدات القواعد $1,5,6$. ستحصل على $3$ ينات وتدفع ينًا واحدًا للإصلاح، ولذلك سيكون ربحك $2$ ين.

الإدخال 2

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

الإخراج 2

3

الإدخال 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

الإخراج 3

5