trang chủ / đề bài / icpc21_mn_h

Tom và Jerry

Đề bài

Mô tả

Tom và Jerry đang rượt đuổi nhau trong một mê cung có dạng cây gồm n đỉnh.

Jerry đang ở đỉnh x và tại đây có một quả bom do Tom đặt. Quả bom có tầm nổ t: khi phát nổ, mọi đỉnh có đường đi đến đỉnh x gồm không quá t+1 đỉnh (tức là không quá t cạnh) đều bị thiêu cháy. Nếu Jerry bị cháy, cậu sẽ ngất xỉu và bị Tom bắt.

Dĩ nhiên Jerry muốn thoát khỏi vùng nổ bằng cách chạy dọc theo các cạnh của mê cung. Ngược lại, Tom muốn bắt Jerry nên định chặn một vài cạnh của mê cung để Jerry không thể đi qua các cạnh đó.

Yêu cầu: Cho m truy vấn, mỗi truy vấn gồm hai số x và t: đỉnh mà Jerry và quả bom đang ở, và tầm nổ của quả bom. Với mỗi truy vấn, hãy giúp Tom tìm số cạnh ít nhất cần chặn để bắt được Jerry, tức là để Jerry không thể chạy tới bất kỳ đỉnh nào nằm ngoài vùng bị thiêu cháy.

Dữ liệu vào

  • Dòng đầu tiên chứa hai số nguyên n, m: số đỉnh của mê cung và số truy vấn.
  • n−1 dòng tiếp theo, mỗi dòng chứa hai số nguyên u, v (1≤u,v≤n, u≠v) cho biết có một cạnh nối u và v.
  • m dòng tiếp theo, mỗi dòng chứa hai số nguyên x, t (1≤x≤n, 0≤t≤n) mô tả một truy vấn.

Dữ liệu ra

Với mỗi truy vấn, in ra trên một dòng số cạnh ít nhất mà Tom cần chặn.

Ràng buộc

  • 1≤n,m≤105.
  • 1≤u,v≤n, u≠v; các cạnh tạo thành một cây.
  • 1≤x≤n, 0≤t≤n.

Ví dụ

Input Output Giải thích
7 3
1 2
2 3
2 4
3 5
3 6
4 7
4 1
2 2
2 1
1
0
2
Truy vấn 1: vùng cháy là các đỉnh 4,2,7; chặn cạnh (4,2) là đủ. Truy vấn 2: mọi đỉnh đều cháy, không cần chặn. Truy vấn 3: vùng cháy là 2,1,3,4; phải chặn hai cạnh (2,3) và (2,4).
1 2
1 0
1 1
0
0
Mê cung chỉ có một đỉnh nên Jerry không có chỗ nào để chạy.

Bình luận

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

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