Truy vấn khoảng cách

Đ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. Trả lời $q$ truy vấn: với mỗi truy vấn $(a, b)$ , tính khoảng cách giữa đỉnh $a$ và đỉnh $b$ (số cạnh trên đường đi từ $a$ đến $b$ ).

Dữ liệu vào

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

$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.
$q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a$ và $b$ .

Dữ liệu ra

Với mỗi truy vấn, in ra khoảng cách giữa $a$ và $b$ .

Ràng buộc

$1 \leq n, q \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 2 4 4 5 1 4	3 2 2	Khoảng cách từ 2 đến 4 là 3 (2→1→3→4). Từ 4 đến 5 là 2 (4→3→5). Từ 1 đến 4 là 2 (1→3→4).
3 2 1 2 2 3 1 3 1 2	2 1	Từ 1 đến 3: đi qua đỉnh 2. Từ 1 đến 2: cạnh trực tiếp.

Bình luận

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