전력 발전소

JOI 발전소에는 1부터 $N$까지 번호가 붙은 $N$개의 거점이 있습니다. 거점들은 $N-1$개의 전선으로 연결되어 있습니다. $i$번째 전선($1 \le i \le N-1$)은 거점 $A_i$와 거점 $B_i$를 양방향으로 잇습니다. 어느 거점에서든 일부 전선을 지나 다른 모든 거점으로 이동할 수 있습니다.

각 거점에는 발전기가 최대 하나 있고, 각 발전기에는 스위치가 있습니다. 처음에는 모든 발전기의 스위치가 꺼져 있습니다. 당신은 발전소의 책임자입니다. 일부 발전기를 골라 스위치를 켤 수 있습니다. 아무것도 고르지 않아도 됩니다. 발전기에는 다음 성질이 있습니다.

• 거점 $x$, $y$, $z$에 발전기가 있고, 같은 전선을 두 번 지나지 않고 $x$에서 $y$로, 이어서 $y$에서 $z$로 이동할 수 있다고 합시다. 이때 $x$와 $z$의 발전기 스위치가 모두 켜져 있으면, $y$의 발전기는 고장납니다.
• 발전기는 스위치가 켜져 있고 고장나지 않았을 때 작동합니다.

작동한 발전기 하나당 1엔의 보상을 받습니다. 고장난 발전기 하나당 1엔의 수리비를 냅니다. 이익은 보상의 합에서 수리비의 합을 뺀 값입니다.

거점, 전선, 발전기 정보가 주어질 때 이익의 최댓값을 구하는 프로그램을 작성하세요.

첫 줄에 $N$이 주어집니다. 이어지는 $N-1$개의 줄에는 각각 $A_i$와 $B_i$가 주어집니다. 마지막 줄에는 길이 $N$인 문자열 $S$가 주어집니다.

N
A_1 B_1
...
A_{N-1} B_{N-1}
S

$S$의 $i$번째 문자는 거점 $i$를 나타냅니다. 발전기가 없으면 0, 있으면 1입니다.

발전기를 골라 스위치를 켰을 때의 이익 최댓값을 표준 출력에 한 줄로 출력하세요.

• $1 \le N \le 200\,000$.
• $S$는 B와 W로 이루어진 길이 $2N$의 문자열입니다. 문자 B는 $S$에 $N$번, 문자 W는 $S$에 $N$번 나타납니다.