페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8509
서브태스크

ABBC 만들기 3s 1024MB

문제

정점이 N개인 트리가 주어진다.

트리의 각 정점에는 1부터 N까지의 번호가 매겨져 있으며, 알파벳 A, B, C 중 하나가 쓰여 있다.

이때 다음 조건을 만족하는 (a, b) 순서쌍의 개수를 구하여라. (1 \leq a < b \leq N) 

  • 정점 a에서 정점 b까지 가는 단순 경로에 포함된 모든 정점에 쓰인 문자들을 모은 뒤
    재배열하여 ABBC가 여러 번 반복하는 문자열(ABBC, ABBCABBC, ...)을 만들 수 있다.

단순 경로란 같은 정점을 여러 번 방문하지 않는 경로를 의미한다.


입력

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

두 번째 줄에는 알파벳 A, B, C로만 이루어진 길이 N짜리 문자열 S가 주어진다.
S의 i번째 문자는 정점 i에 적힌 문자를 의미한다.

세 번째 줄부터 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) 순서쌍의 개수를 출력한다.


부분문제

번호 점수 조건
#116점

N \le 1\,000

#228점

트리의 모양이 직선형이다. 즉, 트리 내에 길이가 N-1인 단순 경로가 존재한다.

#331점

트리의 지름이 4 이하이다. 즉, 트리 내에 길이가 5 이상인 단순 경로가 존재하지 않는다.

#425점

추가 제약 조건은 없다.


예제 #1

5
ABBCC
2 3
4 3
3 5
2 1
2

예제 #2

13
BCCCBBBBABBAA
1 2
2 3
4 7
3 10
6 2
7 6
12 13
9 7
7 8
11 12
7 11
5 7
3


출처

UCPC 2021 예선 - J

로그인해야 코드를 작성할 수 있어요.