Tổng khoảng cách trên cây

Buổi 67-68 — Mock IOI
Points
100
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions

Đề 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
Draft saved