레이팅 미적용*참고: 이 문제의 시간 제한은 기본값의 두 배인 4초이다. 메모리 제한도 기본값의 두 배이다.*
농부 존의 농장에는 \(1 \dots N\)의 번호가 붙은 \(N\)개의 헛간(\(2 \leq N \leq 2\cdot 10^5\))이 있다. \(N-1\)개의 도로가 있으며, 각 도로는 두 헛간을 연결하고, 어떤 헛간에서든 도로들을 따라 다른 어떤 헛간으로도 갈 수 있다. 현재 \(j\)번째 헛간에는 건초 더미가 \(h_j\)개(\(1\le h_j\le 10^9\)) 있다.
소들을 기쁘게 하기 위해, 농부 존은 각 헛간의 건초 더미 개수가 모두 같아지도록 건초를 옮기고 싶다. 그는 도로로 연결된 헛간 쌍 하나를 골라, 첫 번째 헛간에 현재 있는 건초 더미 개수 이하의 양의 정수 개만큼의 건초 더미를 첫 번째 헛간에서 두 번째 헛간으로 옮기라고 일꾼들에게 지시할 수 있다.
농부 존이 최소 횟수의 지시로 작업을 완료할 수 있는 지시의 순서를 구하시오. 지시의 순서가 존재함은 보장된다.
출제: Aryansh Shrivastava
배점
- 테스트 케이스 2-8은 \(N\leq 5000\)을 만족한다.
- 테스트 케이스 7-10은 \(v_i=u_i+1\)을 만족한다.
- 테스트 케이스 11-16은 추가 제약이 없다.
출제: Aryansh Shrivastava
입력의 첫째 줄에 \(N\)의 값이 주어진다.
입력의 둘째 줄에 \(j = 1 \dots N\)에 대한 \(h_j\)의 값이 공백으로 구분되어 주어진다.
입력의 마지막 \(N-1\)개의 줄에는 각각 공백으로 구분된 두 헛간 번호 \(u_i \ v_i\)가 주어지며, 이는 \(u_i\)와 \(v_i\)를 연결하는 양방향 도로가 있음을 나타낸다.
가능한 최소 지시 횟수를 출력한 뒤, 그 길이의 지시 순서를 한 줄에 하나씩 출력한다.
각 지시는 공백으로 구분된 세 개의 양의 정수로 이루어진다. 출발 헛간, 도착 헛간, 그리고 세 번째는 출발 헛간에서 도착 헛간으로 옮길 건초 더미의 개수이다.
답이 여러 개인 경우, 아무거나 출력한다.
4
2 1 4 5
1 2
2 3
2 43
3 2 1
4 2 2
2 1 1In this example, there are a total of twelve hay bales and four barns, meaning
each barn must have three hay bales at the end. The sequence of orders in the
sample output can be verbally translated as below:
- From barn \(3\) to barn \(2\), move \(1\) bale.
- From barn \(4\) to barn \(2\), move \(2\) bales.
- From barn \(2\) to barn \(1\), move \(1\) bale.
riseoj 작성
출처 올림피아드 > USACO > 2022-2023 > December > Silver