Cây Chuồng

Farmer John quản lý $N$ chuồng bò ($2\le N\le 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\le h_j\le {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\le N\le 2\times {10}^5$
• $1\le h_j\le {10}^9$
• Tổng $h_j$ chia hết cho $N$

Ví dụ