회사 문화 스페셜 저지 서브태스크 3초 512MB
문제
n명의 회사원이 있고, 그 중 하나는 디렉터입니다.
디렉터를 제외한 각 직원들에게는 정확히 한 명의 직속 상사가 있습니다.
각 직원은 엄격하게 분리된 업무를 수행합니다.
a 직원이 b 직원이 하고 있는 작업을 수행해야 하는 경우 b 직원에게 요청을 보내야 합니다.
회사 정책에 따르면 작업은 직원에서 직속 상사에게만 직접 이전되거나 그 반대로 관리자에서 직속 부하에게만 이전될 수 있습니다.
요청은 직원 b에 도달할 때까지 직원에서 직원으로 전달됩니다.
직원을 내리기 위해 회사는 k명의 비서를 고용했습니다.
i번 비서는 ai와 bi의 직원 쌍에게 할당되어 그들 사이에 요청을 전달합니다.
이 쌍의 한 직원이 작업을 다른 직원에게 이전해야 하는 경우 해당 작업이 필요한 모든 중간 직원을 통과하고 해당 직원에게 전달될 때까지 직원 간에 작업을 순차적으로 전송하는 비서에게 전달됩니다.
하나의 작업을 전달하는 동안 비서는 동일한 직원을 두 번 이상 방문하지 않습니다.
비용을 최적화하기 위해 경로가 가장 많이 겹치는 한 쌍의 비서를 찾아 그 중 하나를 해고하고 작업을 두 번째에게 맡기기로 결정했습니다.
한 쌍의 비서에 대한 '일치도'를 각 비서가 전달하는 경로에서 일치하는 간선의 개수라고 합니다.
이 때, 일치도가 가장 높은 두 비서를 결정하는 프로그램을 작성해야 합니다.
입력
첫 번쨰 줄에는 n과 k가 공백으로 구분되어 주어집니다.
두 번째 줄에는 n-1개의 수가 공백으로 구분되어 주어집니다. i번째 수는 i+1번 직원의 직속 상사의 번호인 pi를 뜻합니다. (1 <= pi < i+1)
이어지는 k개의 줄에는 ai와 bi가 공백으로 구분되어 주어집니다.
부분문제
#1(41점) : 2 <= n <= 4000, 2 <= k <= 1000
#2(49점) : 2 <= n <= 100000, 2 <= k <= 50000
#3(10점) : 2 <= n <= 200000, 2 <= k <= 200000
출력
첫 번째 줄에는 일치도가 가장 높은 두 비서의 일치도를 출력하세요.
두 번째 줄에는 그 두 비서의 번호를 각각 출력하세요.
예제 #1
4 2
1 2 2
1 3
1 4
1
2 1
예제 #2
4 2
1 2 3
1 2
3 4
0
1 2
예제 #3
7 3
1 2 2 4 5 5
1 3
3 7
6 1
2
2 3
예제 #4
4 3
1 2 3
1 4
4 1
1 4
3
2 1
로그인해야 코드를 작성할 수 있어요.