25123번 - 좋은 단순 경로 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1.5 초 (하단 참고) | 512 MB | 76 | 24 | 20 | 29.412% |
문제
노드가 $n$개인 트리 $T$가 있다. 노드는 $1$부터 $n$까지 번호가 붙어있고, 각 노드에는 영문 대문자 알파벳 ('A' - 'Z') 레이블이 붙어있다. Bob은 $T$에서 길이가 가장 긴 단순 경로를 찾는 문제에 관심이 많다. 단순 경로란, 그래프/트리의 같은 노드를 두 번 이상 방문하지 않는 경로를 말한다.
옆에서 지켜보던 Alice는 Bob에게 아래 정의에 따라 "좋은 단순 경로"를 찾아보라고 했다. 임의의 단순 경로 $P$에 대해, 만약 $P$에 속한 노드들의 레이블을 순서대로 나열하여 문자열을 만들었을 때 같은 알파벳이 연속으로 반복되지 않으면 $P$를 "좋은 단순 경로"라 한다.
예를 들어 위의 트리는 $7$개의 노드를 포함하고 있다.
- 경로 $1 \to 5 \to 7$은 노드 $3$개를 포함하는 단순 경로이지만 노드들의 알파벳을 나열하면 "
AAZ"가 되어 'A'가 연속으로 반복되므로 "좋은 단순 경로"가 아니다. - 경로 $3 \to 2 \to 1$은 노드 $3$개를 포함하는 좋은 단순 경로이다. 노드들의 알파벳을 나열하면 "
AXA"가 되고 같은 알파벳이 여러 번 등장하지만 연속으로 반복되지 않는다. - 경로 $3 \to 2 \to 1 \to 4$와 경로 $4 \to 1 \to 2 \to 3$은 노드 $4$개를 포함하는 좋은 단순 경로이다. 단, 이 두 개의 경로는 같은 노드들을 포함하므로 같은 경로로 간주한다. (예제 입출력 참고)
- 경로 $7$ 혹은 경로 $4$ 처럼 노드를 $1$개만 포함하는 좋은 단순 경로도 존재한다.
- 이 트리에서 가장 긴 좋은 단순 경로의 길이는 $4$이며, 길이가 $4$인 좋은 단순 경로는 단 하나 존재한다.
Alice와 Bob은 $T$에서 가장 긴 좋은 단순 경로의 길이가 무엇인지, 그리고 가장 긴 좋은 단순 경로의 개수가 몇 개인지 궁금해졌다. 둘을 도와 이 문제를 풀어보자.
입력
첫 줄에 테스트 케이스의 수 $T$가 주어진다
각 테스트 케이스는 세 줄에 걸쳐 주어진다. 첫 줄에 노드의 개수 $n$이 주어진다. 둘째 줄에 각 노드의 알파벳 레이블이 공백없이 길이 $n$인 문자열 형태로 주어진다. 셋째 줄에 각 노드의 부모 노드의 번호가 공백으로 구분되어 주어진다. 루트 노드의 부모는 $0$번으로 주어진다.
출력
각 테스트 케이스의 정답인 두 정수를 공백으로 구분하여 각 줄에 출력한다.
첫 번째 정수는 가장 긴 좋은 단순 경로의 길이 (노드의 수)를 나타내고, 두 번째 수는 서로 다른 좋은 단순 경로의 개수를 나타낸다.
제한
- $1 ≤ T ≤ 10$
- 각 노드의 레이블은 알파벳 대문자 ('
A' - 'Z')이다.
서브태스크 1 (10점)
- $1 ≤ n ≤ 1\,000$
서브태스크 2 (20점)
- $1 ≤ n ≤ 100\,000$
예제 입력 1
6 7 AXAYABZ 0 1 2 1 1 5 5 7 QXZQQPZ 0 1 2 1 1 5 5 5 LGBOJ 4 4 4 0 4 5 AAABC 3 3 0 1 2 7 GGGGGGG 0 1 2 1 1 5 5 10 UUQYQYQQQU 3 8 8 8 2 8 3 0 6 8
예제 출력 1
4 1 3 2 3 6 2 2 1 7 5 1
예제 1: 본문에서 다루었다.
예제 2: 노드의 알파벳 레이블을 제외하면 예제 1의 트리와 구조가 같다. 길이가 $3$인 두 개의 좋은 단순 경로는: $1\to 2 \to 3$과 $6 \to 5 \to 7$이다.
예제 3: 이 트리의 길이 $3$인 모든 단순 경로가 좋은 단순 경로이다.
예제 4: $1 \to 4$와 $2 \to 5$ 두 개의 좋은 단순 경로가 가장 긴 단순 경로이다.
예제 5: 본문에서 언급된 것 처럼 길이가 $1$인 좋은 단순 경로도 존재할 수 있다.
시간 제한
- Java 8: 3 초
- Python 3: 4 초
- PyPy3: 4 초
- Java 8 (OpenJDK): 3 초
- Java 11: 3 초
- Kotlin (JVM): 3 초
- Java 15: 3 초
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호