Cây Chuồng

Điểm: 1,00 (OI)

Giới hạn thời gian: 4.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Farmer John quản lý $N$ chuồng bò ( $2 \leq N \leq 2 \times 10^{5}$ ) được nối với nhau bởi $N - 1$ con đường tạo thành cấu trúc cây. Chuồng thứ $j$ chứa $h_{j}$ bó cỏ ( $1 \leq h_{j} \leq 10^{9}$ ). Tổng số bó cỏ chia hết cho $N$ .

Farmer John cần phân phối lại cỏ sao cho mỗi chuồng có số bó cỏ bằng nhau. Anh ta có thể ra lệnh vận chuyển cỏ giữa hai chuồng kề nhau. Mỗi lệnh chỉ định chuồng nguồn, chuồng đích, và số bó cỏ cần chuyển (không vượt quá số cỏ hiện có tại chuồng nguồn).

Hãy tìm số lệnh vận chuyển tối thiểu và đưa ra một cách thực hiện hợp lệ.

Dữ liệu vào

Dòng 1: số nguyên $N$ .
Dòng 2: $N$ số nguyên $h_{1}, h_{2}, \dots, h_{N}$ .
$N - 1$ dòng tiếp theo: mỗi dòng chứa hai số nguyên $u_{i}, v_{i}$ mô tả một cạnh.

Dữ liệu ra

Dòng 1: số lệnh vận chuyển tối thiểu $K$ .
$K$ dòng tiếp theo: mỗi dòng chứa ba số nguyên: chuồng nguồn, chuồng đích, số bó cỏ.

Ràng buộc

$2 \leq N \leq 2 \times 10^{5}$
$1 \leq h_{j} \leq 10^{9}$
Tổng $h_{j}$ chia hết cho $N$

Ví dụ

Input	Output	Giải thích
4 2 1 4 5 1 2 2 3 2 4	3 3 2 1 4 2 2 2 1 1	Tổng = 12, trung bình = 3. Chuyển 1 bó từ chuồng 3 sang 2, 2 bó từ chuồng 4 sang 2, rồi 1 bó từ chuồng 2 sang 1.

Bình luận

Không có bình luận tại thời điểm này.