Dạo chơi đồng cỏ

View as PDF
Submit solution
Points: 0.13 (partial)
Time limit: 0.38s
Memory limit: 512M
Input: stdin
Output: stdout
Problem source:
USACO October 2008 - Qualifying Round
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Có ~N~ con bò ~(1 \le N \le 1000)~, để thuận tiện ta đánh số từ ~1 \rightarrow N~, đang ăn cỏ trên ~N~ đồng cỏ, để thuận tiện ta cũng đánh số các đồng cỏ từ ~1 \rightarrow N~. Biết rằng con bò ~i~ đang ăn cỏ trên đồng cỏ ~i~.

Một vài cặp đồng cỏ được nối với nhau bởi ~1~ trong ~N-1~ con đường ~2~ chiều mà các con bò có thể đi qua. Con đường ~i~ nối ~2~ đồng cỏ ~A_i~ và ~B_i~ ~(1 \le A_i \le N~; ~1 \le B_i \le N)~ và có độ dài là ~L_i~ ~(1 \le L_i \le 10000)~.

Các con đường được thiết kế sao cho với ~2~ đồng cỏ bất kỳ đều có duy nhất ~1~ đường đi giữa chúng. Như vậy các con đường này đã hình thành ~1~ cấu trúc cây.

Các chú bò rất có tinh thần tập thể và muốn được thăm thường xuyên. Vì vậy lũ bò muốn bạn giúp chúng tính toán độ dài đường đi giữa ~Q~ ~(1 \le Q \le 1000)~ cặp đồng cỏ (mỗi cặp được mô tả là ~2~ số nguyên ~p_1, p_2~ ~(1 \le p_1 \le N; 1 \le p_2 \le N).~

Input

  • Dòng ~1~: ~2~ số nguyên cách nhau bởi dấu cách: ~N~ và ~Q~
  • Dòng ~2~...~N~: Dòng ~i+1~ chứa ~3~ số nguyên cách nhau bởi dấu cách: ~A_i, B_i~ và ~L_i~
  • Dòng ~N+1~...~N+Q~: Mỗi dòng chứa ~2~ số nguyên khác nhau cách nhau bởi dấu cách mô tả ~1~ yêu cầu tính toán độ dài đường đi giữa ~2~ đồng cỏ mà lũ bò muốn đi thăm qua lại ~p_1~ và ~p_2~.

Output

  • Dòng ~1~...~Q~: Dòng ~i~ chứa độ dài đường đi giữa ~2~ đồng cỏ ở yêu cầu thứ ~i~.

Sample Input

4 2
2 1 2
4 3 2
1 4 3
1 2
3 2

Sample Output

2
7

Note

Yêu cầu ~1~: Con đường giữa đồng cỏ ~1~ và ~2~ có độ dài là ~2~.

Yêu cầu ~2~: Đi qua con đường nối đồng cỏ ~3~ và ~4~, rồi tiếp tục đi qua con đường nối đồng cỏ ~4~ và ~1~, và cuối cùng là con đường nối đồng cỏ ~1~ và ~2~, độ dài tổng cộng là ~7~.

Comments

Please read the guidelines before commenting.


  • 0
    khoangvan46  commented on April 17, 2025, 3:09 a.m.

    bài này mình dùng dijkstra vẫn AC, LCA thì nhanh hơn


  • 1
    dex111222333444555  commented on March 9, 2025, 2:15 a.m.

    Trong đây có nhiều dạng bài cơ bản về LCA, các bạn nên vào đây tham khảo sẽ trước sẽ tốt hơn giải bài này trước. https://wiki.vnoi.info/vi/algo/data-structures/lca-binlift


  • 1
    blobbyghost01  commented on Jan. 20, 2025, 2:26 p.m. ← edited

    Bạn nào bị segmentation fault test cuối thì lưu ý giới hạn bài này là N<=1004 chứ ko phải 1000 đâu đề trôn vl


  • 1
    anhquan04  commented on Jan. 2, 2025, 11:32 a.m. ← edited

    hi mn


  • 2
    so100000  commented on Dec. 2, 2024, 1:38 a.m.

    nên đọc qua phần lca trước khi làm bai này nha


  • 0
    HaoHaoChuaCay  commented on Sept. 7, 2024, 4:47 p.m.

    mọi người cho mình hỏi là sao mình dùng thuật toán lca logn thì lại sai test cuối ạ, hoặc ai có test cuối thì cho mình xin xem sai ở đâu ạ


  • -16
    hoanglongnguyen9002  commented on Aug. 29, 2024, 3:55 a.m. ← edited

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -17
    hoanglongnguyen9002  commented on Aug. 29, 2024, 3:55 a.m. ← edited

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -6
    levanhuyluc  commented on Aug. 23, 2024, 4:19 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -21
    khanhlani  commented on Aug. 2, 2024, 1:49 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • -15
      hieuz08  commented on Aug. 2, 2024, 8:39 a.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


      • -14
        khanhlani  commented on Aug. 2, 2024, 8:53 a.m.

        This comment is hidden due to too much negative feedback. Show it anyway.


        • 0
          longhoangho  commented on March 17, 2025, 11:37 a.m.

          Khánh nguyên là của mọi người


  • 7
    tboros2  commented on July 13, 2023, 7:10 a.m.

    LCA: https://vnoi.info/wiki/algo/data-structures/lca-binlift.md#b%C3%A0i-to%C3%A1n-1-1


  • -72
    MrMinhFly  commented on May 13, 2021, 1:28 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.