Sau khi được học về cây tìm kiếm nhị phân (BST - Binary Search Tree), Nghĩa rất thích thú với cấu trúc dữ liệu này và quyết định tạo ra một cấu trúc dữ liệu cho riêng mình, đặt tên là ABST. Cụ thể, cấu trúc dữ liệu ABST có dạng là một cây nhị phân và mỗi nút đều được gán một khóa sao cho với mỗi nút :
Mọi khóa trên cây con trái đều nhỏ hơn hoặc bằng khóa trên nút ;
Mọi khóa trên cây con phải đều lớn hơn hoặc bằng khóa trên nút .
Một lần, Nghĩa bắt gặp một hình vẽ là một cây nhị phân, trên mỗi nút có một khóa là một số nguyên. Nghĩa tò mò điều chỉnh giá trị khóa tại các nút để cây nhận được có tính chất như cây ABST. Mỗi bước Nghĩa được phép tăng hoặc giảm giá trị khóa đi một đơn vị ở một nút.
Yêu cầu: Hãy tính số bước ít nhất giúp Nghĩa điều chỉnh giá trị khóa tại các nút để cây nhận được có tính chất như cây ABST.
Dữ liệu vào:
Dòng đầu chứa số nguyên là số nút của cây;
Tiếp theo là dòng, dòng thứ chứa ba số nguyên không âm , trong đó là giá trị khóa trên nút , là nút con trái, là nút con phải. Nếu có nghĩa nút không có con trái, tương tự, nếu nghĩa là nút không có con phải.
Dữ liệu ra:
Gồm một dòng chứa một số nguyên là số bước ít nhất giúp Nghĩa điều chỉnh giá trị khóa tại các nút để cây nhận được có tính chất như cây ABST. Lưu ý rằng, cây sau khi điều chỉnh giá trị khóa ở các nút có thể âm.
