CSES - Counting Paths | Đếm đường đi

Xem PDF

Điểm: 1600 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho một cây có \(n\) nút, các nút trên cây được đánh số lần lượt là \(1,2,3,...,n\)\(m\) con đường.

Nhiệm vụ của bạn là với mỗi nút, hãy đếm số đường đi chứa nút này.

Input:

  • Dòng đầu tiên chứa 2 số \(n\)\(m\).
  • \(n - 1\) dòng tiếp theo, mỗi dòng chứa chứa 2 số \(a\)\(b\), thể hiện rằng có một cạnh nối hai nút \(a\)\(b\).
  • \(m\) dòng cuối, mỗi dòng chứa 2 số \(a\)\(b\), thể hiện rằng có một con đường từ nút \(a\) tới \(b\).

Output:

  • In ra \(n\) số: số lượng đường đi qua mỗi nút \(1,2,3,\dots,n\).

Constraints:

  • \(1 ≤ n, m ≤ 2 \cdot 10 ^ 5\)
  • \(1 ≤ a, b ≤ n\)

Example:

Sample Input:

5 3
1 2
1 3
3 4
3 5
1 3
2 5
1 4

Sample Output:
3 1 3 1 1


Bình luận (1)

Sắp xếp theo
Tải bình luận...