22360번 - UCPC 만들기

정점이 $N$개인 트리가 주어진다. 트리의 각 정점에는 1부터 $N$까지의 번호가 매겨져 있으며, 알파벳 U, C, P 중 하나가 쓰여 있다. 이때 다음 조건을 만족하는 $(a, b)$ 순서쌍의 개수를 구하여라. $(1 \leq a < b \leq N)$

• 정점 $a$에서 정점 $b$에 이르는 단순 경로에 포함된 모든 정점에 쓰인 문자들을 모은 뒤 재배열하여 $($UCPC$)^k$ 꼴의 문자열을 만들 수 있다. ($k \geq 1$)

첫 번째 줄에는 정점의 개수 $N$이 주어진다. $(1 \leq N \leq 200\ 000)$

그 다음 줄에는 알파벳 U, C, P로만 이루어진 길이 $N$의 문자열 $S$가 주어진다.

그 다음 $N-1$개의 줄에 걸쳐 두 정수 $u_i$와 $v_i$가 공백으로 구분되어 주어진다. 이는 트리에서 정점 $u_i$와 정점 $v_i$가 직접 연결되어 있음을 의미한다. $(1 \leq u_i, v_i \leq N, u_i \neq v_i)$

조건을 만족하는 $(a, b)$ 순서쌍의 개수를 출력한다.

예제 1에 해당하는 트리는 아래와 같다.

그림 J.1: 예제 1에 해당하는 트리

1번 정점과 4번 정점, 1번 정점과 5번 정점 사이의 경로를 이용하면 $k=1$ 형태의 문자열(UCPC)을 만들 수 있다.

예제 2의 경우, $k=1$ 형태의 문자열(UCPC) 2개, $k=2$ 형태의 문자열(UCPCUCPC) 1개를 만들 수 있다.