| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 219 | 84 | 77 | 39.086% |
$1$부터 $N$까지 번호가 붙은 $N$개 정점으로 이루어진 두 개의 트리 $T_1$, $T_2$가 주어진다. 서로 다른 양의 정수 $s$, $e$에 대해 각 트리에서 $s$번 정점에서 $e$번 정점으로 가는 최단 경로를 생각하자. 두 트리에서 최단 경로를 이루는 정점들의 번호 순서가 완전히 동일할 때, 그 경로를 두 트리의 공통 경로(Common Path)라고 정의한다. 이때 공통 경로의 길이는 $s$번 정점과 $e$번 정점을 잇는 최단 경로에 포함되는 간선의 수이다.
두 트리에서 찾을 수 있는 공통 경로 중 가장 길이가 긴 것을 하나 찾는 프로그램을 작성하시오.
첫째 줄에 $T_1$, $T_2$의 정점의 개수를 나타내는 양의 정수 $N$이 주어진다.
둘째 줄부터 $N-1$개 줄에 걸쳐 $T_1$를 구성하는 간선들의 정보가 주어진다. 각 줄에는 각 간선이 연결하는 두 정점의 번호 $u$, $v$가 공백으로 구분되어 주어진다.
이어서 $N-1$개 줄에 걸쳐 $T_2$를 구성하는 간선들의 정보가 주어진다. 각 줄에는 각 간선이 연결하는 두 정점의 번호 $u$, $v$가 공백으로 구분되어 주어진다.
첫째 줄에 가장 긴 공통 경로의 양 끝 정점의 번호 $s$, $e$를 공백으로 구분하여 출력한다. 만약 가장 긴 공통 경로가 여러 개여도 하나만 출력하면 된다.
만약 길이가 $1$ 이상인 공통 경로가 존재하지 않는다면, -1을 출력한다.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 11 | 공통 경로가 존재할 경우, 길이가 반드시 1이다. |
| 2 | 27 | $N \leq 1000$ |
| 3 | 62 | 추가 제한 조건이 없습니다. |
8 1 2 1 3 1 4 2 5 2 6 2 7 5 8 1 2 1 3 2 4 2 5 3 6 4 7 5 8
8 3
트리는 사이클이 없는 연결 그래프이다.
School > 서울과학고등학교 > SciOI 2025 C번