문제
1…N으로 번호가 매겨진 N개의 병영이 있고,각 병영을 연결하는 N-1개의 길이 있으며, j 번째 병영에는 aj명의 병사가 배치되어있다.
모든 병영에 동일한 수의 병사가 있도록 옮기기 위하여 길로 연결된 한 쌍의 병영을 선택하고 첫 번째 병영에 있는 병사의 수보다 작거나 같은 양의 병사를 첫 번째 병영에서 두 번째 병영으로 옮기도록 할 수 있다.
작업을 완료하기 위해 필요한 최소 횟수를 출력하시오. 답이 있음이 보장된다.
입력
첫 번째 줄에 N이 입력된다 (2≤N≤2⋅105).
두 번째 줄에 j=1…N에 해당하는 aj가 공백을 기준으로 입력된다 (1≤aj≤109).
세 번째 줄부터 N-1개의 줄에 걸쳐 길로 연결된 두 병영이 입력된다.
출력
최소 이동 횟수를 출력하고, 한 줄에 하나씩 해당 횟수 만큼의 이동 순서를 출력하시오.
각 이동은 세 개의 공백으로 구분된 양의 정수 A, B, C로 나타내야한다.
A는 출발 병영, B는 도착 병영, C는 이동시킬 병사의 수를 나타낸다.
답이 여러 개인 경우 아무거나 출력합니다.
예제1
입력
4
2 1 4 5
1 2
2 3
2 4
출력
3
3 2 1
4 2 2
2 1 1
힌트
태그
출처
USACO 2022 December Silver