trang chủ / đề bài / lcabin

Khoảng cách trên cây có trọng số

Đề bài

Mô tả

Cho một cây có gốc tại đỉnh 1 gồm N đỉnh, được mô tả bởi N−1 cạnh. Mỗi cạnh nối hai đỉnh u và v và có trọng số w (số nguyên dương).

Cho Q truy vấn. Trong mỗi truy vấn cho hai đỉnh ui và vi, hãy in tổng trọng số các cạnh trên đường đi đơn giản từ ui tới vi trên cây.

Dữ liệu vào

  • Dòng đầu tiên chứa hai số nguyên N và Q.
  • N−1 dòng tiếp theo, mỗi dòng chứa ba số nguyên u, v, w mô tả một cạnh nối hai đỉnh u và v có trọng số w.
  • Q dòng tiếp theo, mỗi dòng chứa hai số nguyên ui và vi.

Dữ liệu ra

In ra Q dòng. Dòng thứ i chứa khoảng cách từ ui tới vi (tổng trọng số các cạnh trên đường đi).

Ràng buộc

  • 1≤N≤105
  • 1≤Q≤105
  • 1≤u,v≤N
  • 1≤w≤104
  • Dữ liệu đảm bảo các cạnh tạo thành một cây có gốc 1.

Ví dụ

Input Output Giải thích
5 4
1 2 3
1 3 5
2 4 2
2 5 7
4 5
3 5
1 1
4 3		 9
15
0
10		 Đường đi 4→2→5 tổng 2+7=9. Đường đi 3→1→2→5 tổng 5+3+7=15. Đường đi 1→1 là 0. Đường đi 4→2→1→3 tổng 2+3+5=10.
7 3
1 2 4
1 3 6
2 4 1
2 5 9
3 6 2
3 7 8
6 5
4 7
1 6		 21
19
8		 Đường đi 6→3→1→2→5 tổng 2+6+4+9=21. Đường đi 4→2→1→3→7 tổng 1+4+6+8=19. Đường đi 1→3→6 tổng 6+2=8.

Ghi chú

Với N,Q tới 105, thuật toán O(QN) (BFS lại với mỗi truy vấn) sẽ không kịp trong giới hạn thời gian. Bạn nên dùng cấu trúc dữ liệu cho phép trả lời mỗi truy vấn trong O(logN).

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