Elearning CodePath – CTP Online Judge

TREE

🟢 Medium #Tree #BFS/DFS

Cho đồ thị vô hướng liên thông có định (các đỉnh đánh số từ 1 đến n) và n - 1 cạnh. Đỉnh i có trọng số là ( a_i ) (1 ≤ i ≤ n).

Gọi ( M(x, y) ) là trọng số lớn nhất của các đỉnh trên đường đi từ đỉnh x đến đỉnh y và ( S(x, y) ) là tổng trọng số của các đỉnh trên đường đi từ x đến y.

Hãy đếm số cặp ( (x, y) ) thỏa mãn ( x < y ) và:
$2 \times M(x, y) \le S(x, y)$

Dữ liệu vào/ra

| Thành phần | Mô tả                |
| ---------- | -------------------- |
| Input      | Từ file TREE.INP     |
| Output     | Ghi ra file TREE.OUT |

| Input           |                                                         |
| --------------- | ------------------------------------------------------- |
| Dòng 1          | Số nguyên n (1 ≤ n ≤ 2 × 10^5)                          |
| Dòng 2          | n số nguyên ( a_1, a_2, ..., a_n ) (1 ≤ ( a_i ) ≤ 10^9) |
| n - 1 dòng tiếp | Mỗi dòng gồm hai số u, v (1 ≤ u, v ≤ n) là một cạnh     |

| Output        |                        |
| ------------- | ---------------------- |
| Một số nguyên | Số cặp (x, y) thỏa mãn |

Ví dụ

| TREE.INP  | TREE.OUT | Giải thích                               |
| --------- | -------- | ---------------------------------------- |
| 5         | 6        | 6 cặp (x, y) thỏa mãn là:                |
| 1 1 1 1 1 |          | (2,3), (2,4), (2,5), (3,4), (3,5), (4,5) |
| 1 2       |          |                                          |
| 1 3       |          |                                          |
| 1 4       |          |                                          |
| 1 5       |          |                                          |

| TREE.INP   | TREE.OUT | Giải thích                |
| ---------- | -------- | ------------------------- |
| 5          | 3        | 3 cặp (x, y) thỏa mãn là: |
| 10 3 8 1 2 |          | (2,3), (3,4), (3,5)       |
| 1 2        |          |                           |
| 1 3        |          |                           |
| 2 4        |          |                           |
| 2 5        |          |                           |

| Subtask | Ràng buộc                          |
| ------- | ---------------------------------- |
| 1       | n ≤ 1000                           |
| 2       | ( a_i = 1 )                        |
| 3       | Không có đỉnh nào có bậc lớn hơn 2 |
| 4       | n ≤ 50000                          |
| 5       | Không có ràng buộc bổ sung         |

✅ Đã AC: 2 / 7 submissions