trang chủ / bài tập / 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

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.46 awk 1.3.4 gcc 16.1.0 csc 6.12.0.200 g++ 16.1.0 g++-themis 16.1.0 g++17 16.1.0 g++20 16.1.0 g++23 16.1.0 clang++ 22.1.6 dmd 2.112.0 dart 3.12.1 gforth 0.7.3 gfortran 12.2.0 go 1.26.3 groovyc 5.0.6 javac 25.0.3 node 26.2.0 kotlinc 2.3.21 sbcl 2.2.9 lua 5.4.8 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.6 pike 8.0 pypy3 7.3.23 python3 3.14.5 racket 8.7 ruby 4.0.5 rustc 1.96.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 tclsh 8.6 bun 1.3.14 deno 2.8.1 v 0.5.1 zig 0.16.0