trang chủ / đề bài / distqry

Truy vấn khoảng cách

Đề bài

Mô tả

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≤n,q≤2·105
  • 1≤a,b≤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

  • maytinhoc3
    maytinhoc3
    đã bình luận 5 months trước

    Hello

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0