Đếm đường đi qua đỉnh

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho một cây gồm $n$ đỉnh và $m$ đường đi. Mỗi đường đi được xác định bởi hai đỉnh $a$ và $b$ , tương ứng với đường đi duy nhất giữa $a$ và $b$ trên cây.

Với mỗi đỉnh, hãy tính số lượng đường đi đi qua đỉnh đó.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $n$ và $m$ .

$n - 1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a$ và $b$ mô tả một cạnh của cây.
$m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a$ và $b$ mô tả một đường đi.

Dữ liệu ra

In ra $n$ số nguyên, số thứ $i$ là số lượng đường đi đi qua đỉnh $i$ .

Ràng buộc

$1 \leq n, m \leq 2 \cdot 10^{5}$
$1 \leq a, b \leq n$

Ví dụ

Input	Output	Giải thích
5 3 1 2 1 3 3 4 3 5 1 3 2 5 1 4	3 1 3 1 1	Đường đi 1-3 qua đỉnh 1,3. Đường đi 2-5 qua đỉnh 2,1,3,5. Đường đi 1-4 qua đỉnh 1,3,4. Đỉnh 1 và 3 xuất hiện trong cả 3 đường đi.
4 2 1 2 2 3 3 4 1 4 2 3	1 2 2 1	Đường đi 1-4 qua 1,2,3,4. Đường đi 2-3 qua 2,3.

Bình luận

Không có bình luận tại thời điểm này.