누텔라 트리 (Hard)

민제는 정점이 $N$개인 트리를 가지고 있다. 이 트리의 각 정점은 빨간색 또는 검은색으로 칠해져 있다.

민제는 빨간색과 검은색 정점들로 가득한 이 트리를 보고 누텔라(Nutella)를 떠올렸다. 누텔라는 민제가 가장 좋아하는 초콜릿 잼으로, 로고는 다음과 같이 생겼다. 맨 앞 글자는 검은색, 나머지 글자는 빨간색임에 주목하자.

민제는 트리에서 누텔라 로고를 몇 개나 찾을 수 있을지 궁금해졌다.

다음 조건들을 만족하는 서로 다른 정점들의 열 $\[v\_1, v\_2, \cdots\\!, v\_k]$를 누텔라 경로라 정의하자.

• $k$는 $2$ 이상이다.
• 각 $1 \le i \le k-1$에 대해, $v\_i$와 $v\_{i+1}$은 트리에서 간선으로 직접 연결되어 있다.
• $v\_1$은 검은색이다.
• 각 $2 \le i \le k$에 대해, $v\_i$는 빨간색이다.

주어진 트리에서 누텔라 경로가 총 몇 개 있는지 구하시오.

단, 민제는 정점 하나를 골라 색을 바꾸는 작업을 총 $Q$회 수행할 예정이다. 해당 정점이 검은색이었다면 빨간색으로, 빨간색이었다면 검은색으로 색이 바뀐다. 이 작업을 수행할 때마다 누텔라 경로의 개수를 새로 구해야 한다.

첫째 줄에 트리의 정점의 개수 $N$이 주어진다. ($2 \le N \le 100\\,000$)

둘째 줄부터 $(N-1)$개 줄에 걸쳐 각 간선이 잇는 두 정점의 번호 $u\_i$, $v\_i$가 공백을 사이에 두고 주어진다. ($1 \le u\_i \le N$, $1 \le v\_i \le N$, $u\_i \neq v\_i$)

$(N+1)$째 줄에 알파벳 B, R로만 이루어진 길이 $N$의 문자열 $C$가 주어진다. $C$의 $i$번째 문자는 $i$번 정점의 색을 나타내며, B는 검은색, R는 빨간색을 의미한다.

그 다음 줄에 정점의 색을 바꾸는 횟수 $Q$가 주어진다. ($1 \le Q \le 100\\,000$)

그 다음 줄부터 $Q$개 줄에 걸쳐 색을 바꿀 정점의 번호 $q\_i$가 주어진다. ($1 \le q\_i \le N$)

총 $(Q+1)$개 줄에 걸쳐 정답을 출력한다.

첫째 줄에는 맨 처음 주어진 트리에서의 누텔라 경로의 개수를 출력한다.

$(i+1)$번째 줄에는 색을 바꾸는 작업을 $i$회 수행한 이후 누텔라 경로의 개수를 출력한다. ($1 \le i \le Q$)

예제로 주어진 트리의 초기 상태를 그림으로 나타내면 다음과 같다.

$1$번 정점의 색을 바꾸면 트리는 다음과 같이 변한다.