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

Xem PDF
Tác giả:
Flower_On_Stone , haidanghutcansa , An09855
Dạng bài
Đ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\) và \(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\) và \(m\).
  • \(n - 1\) dòng tiếp theo, mỗi dòng chứa chứa 2 số \(a\) và \(b\), thể hiện rằng có một cạnh nối hai nút \(a\) và \(b\).
  • \(m\) dòng cuối, mỗi dòng chứa 2 số \(a\) và \(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


  • 0
    N7hoatt    11:59 a.m. 17 Tháng 8, 2023

    Cho một cây gồm \(n\) đỉnh và \(m\) con đường.

    Với mỗi đỉnh, hãy đếm số đường đi đi qua đỉnh này.

    Input

    • Dòng đầu tiên gồm hai số nguyên \(n\) và \(m\) lần lượt là số đỉnh và số con đường. Các đỉnh được đánh số từ \(1,2,3,\dots,n\).
    • \(n-1\) dòng tiếp theo mỗi dòng gồm hai số nguyên \(a\) và \(b\): có cạnh giữa hai đỉnh \(a\) và \(b\).
    • \(m\) dòng cuối cùng mỗi dòng gồm hai số nguyên \(a\) và \(b\): có con đường từ đỉnh \(a\) tới đỉnh \(b\).

    Output

    • In ra \(n\) số nguyên: số lượng con đường đi qua mỗi đỉnh \(1,2,3,\dots,n\).

    Constraints

    • \(1\leq n,m\leq 2 \times 10^5\).
    • \(1\leq a,b\leq n\).

    Example

    Test

    Input 
    5 3
1 2
1 3
3 4
3 5
1 3
2 5
1 4
    Output 
    3 1 3 1 1
    Note