#2022 · Mạng lưới khoảng cách bí ẩn

Trong một hệ thống mạng thông minh của tương lai, các trạm được kết nối với nhau bằng các tuyến đường đặc biệt tạo thành một cấu trúc cây.

Mỗi tuyến đường có một độ dài (trọng số), và dữ liệu hệ thống chỉ lưu lại khoảng cách giữa các cặp trạm, thay vì cấu trúc kết nối ban đầu.

Do một sự cố, toàn bộ sơ đồ mạng đã bị mất, chỉ còn lại bảng khoảng cách giữa các trạm.

Bạn được cung cấp một số nguyên N - số lượng trạm.

Với mỗi cặp (i, j) $(1 \le i < j \le N)$, bạn biết: $A_{i,j}$ là khoảng cách giữa trạm $i$ và trạm $j$.

Khoảng cách này được định nghĩa là:

\text{dist}(i,j) = \sum \text{trọng số các cạnh trên đường đi duy nhất giữa } i \text{ và } j

Hãy xác định xem: Có tồn tại một cây vô hướng có trọng số dương gồm N đỉnh sao cho mọi khoảng cách thực tế đều đúng bằng A_{i,j} hay không?

• Dòng 1: số nguyên N
• Các dòng tiếp theo:

A_{1,2}, A_{1,3}, \dots, A_{1,N}

A_{2,3}, \dots, A_{2,N}

\dots

A_{N-1,N}

• In Yes nếu tồn tại cây phù hợp\
• Ngược lại in No