Tổng khoảng cách trên cây
Points
100
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Cho một cây gồm $N$ đỉnh đánh số từ $1$ đến $N$. Đỉnh thứ $i$ có trọng số là $a_i$, và mỗi cạnh $(u, v)$ có độ dài là $w$.
Với mỗi đỉnh $u \in {1, 2, \dots, N}$, hãy tính giá trị: \[S(u) = \sum_{v=1}^{N} a_v \cdot \text{dist}(u, v)\] trong đó $\text{dist}(u, v)$ là tổng độ dài các cạnh trên đường đi đơn duy nhất giữa $u$ và $v$.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên $N$ ($1 \le N \le 10^5$).
- Dòng thứ hai chứa $N$ số nguyên $a_1, a_2, \dots, a_N$ ($1 \le a_i \le 10^4$).
- $N - 1$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u, v, w$ ($1 \le u, v \le N$, $1 \le w \le 10^4$) mô tả một cạnh của cây.
Kết quả
In ra $N$ số nguyên $S(1), S(2), \dots, S(N)$ trên một dòng, cách nhau bởi dấu cách.
Subtasks
- Subtask 1 (25%): $N \le 2000$.
- Subtask 2 (35%): Cây là một đường thẳng và $a_i = 1, w = 1$ với mọi đỉnh và cạnh.
- Subtask 3 (40%): Không có ràng buộc thêm.
Ví dụ
| Input | Output |
|---|---|
| 4 1 2 3 4 1 2 1 2 3 2 2 4 3 |
27 19 27 25 |
Community Discussion