CSES - Distance Queries | Truy vấn Khoảng cách

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 gồm \(n\) nút.

Nhiệm vụ của bạn là xử lý \(q\) truy vấn dưới dạng: khoảng cách giữa nút \(a\) và \(b\) bằng bao nhiêu?

Input

  • Dòng đầu vào đầu tiên chứa hai số nguyên \(n\) và \(q:\) số lượng nút và truy vấn. Các nút được đánh số \(1,2,... ,n.\)
  • Sau đó, có \(n−1\) dòng mô tả các cạnh. Mỗi dòng chứa hai số nguyên \(a\) và \(b:\) có một cạnh nối hai nút \(a\) và \(b\).
  • Cuối cùng, có \(q\) dòng mô tả các truy vấn. Mỗi dòng chứa hai số nguyên \(a\) và \(b\) ứng với câu hỏi "Khoảng cách giữa hai nút \(a\) và \(b\) là bao nhiêu?".

Output

  • In ra \(q\) số nguyên\(:\) câu trả lời cho mỗi truy vấn.

Constraints

  • \(1 ≤ n,q ≤ 2⋅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

1
3
2

Bình luận


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

    Cho một cây gồm \(n\) đỉnh.

    Hãy thực hiện \(q\) truy vấn có dạng: tìm khoảng cách giữa hai đỉnh \(a\) và \(b\).

    Input

    • Dòng đầu tiên gồm hai số nguyên \(n\) và \(q\) lần lượt là số đỉnh và số truy vấn. Các đỉnh được đánh số từ \(1,2,3,\dots,n\).
    • \(n-1\) dòng tiếp theo biểu diễn các cạnh. mỗi dòng gồm hai số nguyên \(a\) và \(b\): có cạnh giữa hai đỉnh \(a\) và \(b\);
    • \(q\) dòng cuối cùng biểu diễn các truy vấn. Mỗi dòng gồm hai số nguyên \(a\) và \(b\): tìm khoảng cách giữa hai đỉnh \(a\) và \(b\).

    Output

    • In ra kết quả cho \(q\) truy vấn.

    Constraints

    • \(1\leq n,q\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 
    1
3
2
    Note