시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 771 | 221 | 191 | 32.762% |
민제는 정점이 $N$개인 트리를 가지고 있다. 이 트리의 각 정점은 빨간색 또는 검은색으로 칠해져 있다.
민제는 빨간색과 검은색 정점들로 가득한 이 트리를 보고 누텔라(Nutella)를 떠올렸다. 누텔라는 민제가 가장 좋아하는 초콜릿 잼으로, 로고는 다음과 같이 생겼다. 맨 앞 글자는 검은색, 나머지 글자는 빨간색임에 주목하자.
민제는 트리에서 누텔라 로고를 몇 개나 찾을 수 있을지 궁금해졌다.
다음 조건들을 만족하는 서로 다른 정점들의 열 $[v_1, v_2, \cdots\!, v_k]$를 누텔라 경로라 정의하자.
주어진 트리에서 누텔라 경로가 총 몇 개 있는지 구하시오.
첫째 줄에 트리의 정점의 개수 $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$)
그 다음 줄에는 알파벳 B
, R
로만 이루어진 길이 $N$의 문자열 $C$가 주어진다. $C$의 $i$번째 문자는 $i$번 정점의 색을 나타내며, B
는 검은색, R
는 빨간색을 의미한다.
첫째 줄에 누텔라 경로의 개수를 출력한다.
6 1 3 2 4 5 3 4 6 3 4 RRBRRB
6
예제로 주어진 트리를 그림으로 나타내면 다음과 같다.
University > 서울대학교 > 2021 서울대학교 프로그래밍 경시대회 > Division 2 D번