Đường đi của những kẻ ngốc

Điểm: 6,00 (OI)

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

Python 3 5.0s

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

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Berland có $n$ thành phố, được nối bởi $n - 1$ con đường hai chiều sao cho giữa mỗi cặp thành phố có duy nhất một đường đi đơn (tức là đồ thị tạo thành một cây). Các con đường được đánh số từ $1$ tới $n - 1$ theo thứ tự xuất hiện trong dữ liệu vào.

Có $k$ cặp người, cặp thứ $i$ gồm hai người sống ở thành phố $a_{i}$ và $b_{i}$ . Người thứ $2 i - 1$ đi từ thành phố $a_{i}$ tới gặp người thứ $2 i$ ở thành phố $b_{i}$ theo đường đi đơn duy nhất trong cây.

Với mỗi con đường, hãy đếm xem có bao nhiêu người đã đi qua nó. Một con đường được tính nếu nó nằm trên đường đi đơn của ít nhất một trong hai người trong một cặp; cặp $(a_{i}, b_{i})$ đóng góp giá trị $2$ cho mỗi con đường nằm trên đường đi từ $a_{i}$ tới $b_{i}$ (mỗi người đi qua đúng một lần).

Lưu ý: nếu $a_{i} = b_{i}$ thì không có con đường nào được sử dụng trong cặp đó.

Dữ liệu vào

Dòng đầu chứa số nguyên $n$ — số thành phố.
$n - 1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u_{i}, v_{i}$ ( $1 \leq u_{i}, v_{i} \leq n$ , $u_{i} \neq v_{i}$ ) mô tả con đường nối hai thành phố $u_{i}$ và $v_{i}$ .
Dòng tiếp theo chứa số nguyên $k$ — số cặp người.
$k$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a_{i}, b_{i}$ ( $1 \leq a_{i}, b_{i} \leq n$ ).

Dữ liệu ra

In ra $n - 1$ số nguyên cách nhau bởi khoảng trắng: số thứ $i$ là số người đã đi qua con đường thứ $i$ (theo thứ tự xuất hiện trong dữ liệu vào).

Ràng buộc

$2 \leq n \leq 10^{5}$
$0 \leq k \leq 10^{5}$

Ví dụ

Input	Output	Giải thích
5 1 2 1 3 2 4 2 5 2 1 4 3 5	2 1 1 1	Cặp 1 đi từ 1 tới 4 qua đường 1 (1-2) và 3 (2-4). Cặp 2 đi từ 3 tới 5 qua đường 2 (1-3), 1 (1-2), 4 (2-5). Mỗi người trong cặp đi một lần nên đường 1 được dùng bởi hai người (một từ mỗi cặp).
5 3 4 4 5 1 4 2 4 3 2 3 1 3 3 5	3 1 1 1	Đường 1 (3-4) nằm trên cả ba đường đi $2 \to 3$ , $1 \to 3$ , $3 \to 5$ nên có 3 người đi qua. Mỗi đường còn lại chỉ thuộc một đường đi nên đều bằng 1.

Bình luận

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