문제
트리를 나타내는 간선들의 정보가 주어질 때, 간선 2개를 제거하여 부분 트리 세 개로 만들려고 한다.
이 때, 각 부분트리의 노드 개수가 모두 같아야 한다. 다음은 노드가 9개인 트리의 예시이다.
위 그림에서 동그라미 안에 적힌 숫자는 노드번호, 간선에 적힌 숫자는 간선 번호를 나타낸다.
위 예시와 같이 붉은색 간선(2번, 5번)을 제거하면 세 부분 트리로 나뉘며,
각 부분 트리에 속한 노드 개수는 3개로 모두 같다.
이때, 세 부분으로 분리된 부분 트리는 노드 수만 같으면 되며,
트리의 모양까지 같을 필요는 없다.
트리의 노드 개수와, 트리의 간선 정보가 주어질 때,
노드 수가 같은 부분 트리 세 개로 분리하기 위해 제거해야 하는 두 간선의 번호를
오름차순으로 출력하는 프로그램을 작성하시오.
입력
첫 행에 N (3이상 99이하의 3의 배수)이 주어진다.
각 노드의 번호는 0 ~ N-1 로 번호가 매겨져 있다.
두 번째 행부터 N-1개의 행에 간선의 정보가주어진다.
각 간선의 정보에는 두 개의 노드 번호 a와 b가 공백을 구분하여 주어지는데
a와 b가 연결되어 있다는 의미이다.
간선은 주어진 순서대로 0번 부터 N-2번까지 번호가 부여된다.
정답이 정확이 한 개인 경우만 주어진다.
출력
두 개의 간선을 제거하여 같은 수의 노드들로 구성된
세 개의 부분 트리로 분할 할 때,
제거되는 두 간선 번호를
오름차순으로 공백을 구분하여 하나의 행에 출력한다.
예제
9
0 2
2 1
2 4
3 5
5 4
5 7
7 6
6 8
2 5
힌트
출처
naver2020_2 2번 | dnfka0930
로그인해야 코드를 작성할 수 있어요.