Cho cây gồm n đỉnh, mỗi cạnh có trọng số dương. Với mỗi truy vấn (u,v), hãy tính khoảng cách giữa u và v — tổng trọng số các cạnh trên đường đi duy nhất nối chúng.
Sử dụng nhảy nhị phân (binary lifting) để tìm tổ tiên chung gần nhất (LCA), từ đó tính khoảng cách bằng công thức dist(u,v)=D(u)+D(v)−2D(lca(u,v)), với D(x) là khoảng cách từ gốc tới x.
Dòng đầu chứa n và q. n−1 dòng tiếp theo, mỗi dòng ba số u v w (cạnh u–v trọng số w). q dòng cuối, mỗi dòng hai số u v.
1≤n,q≤2⋅105, 1≤w≤109. Gốc cây là đỉnh 1.
Với mỗi truy vấn, in khoảng cách trên một dòng.
Ví dụ:
Đầu vào:
4 2
1 2 3
1 3 5
3 4 2
2 4
2 3
Đầu ra:
10
8
Giải thích:
Đang tải editor...