Cây nhi: lqdoj c++/pas
Tùng Dương có một cây (đồ thị vô hướng liên thông và không có chu trình) gồm N đỉnh được đánh số từ 1 đến N. Dương đặt tên cây này là cây Nhi. Mỗi cạnh của cây Nhi đều được tô một màu nào đó trong N−1 màu có sẵn (các màu này được đánh mã từ 1 đến N−1). Cạnh thứ i của cây Nhi nối đỉnh ui với đỉnh vi, đồng thời có độ dài di và được tô màu với mã màu là ci. Dương nhờ bạn lập trình trả lời Q truy vấn, trong đó, truy vấn thứ j cho biết bốn số nguyên xj, yj, uj, vj và yêu cầu bạn cập nhật độ dài của tất cả các cạnh được tô màu với mã màu xj thành yj, sau đó in ra khoảng cách giữa đỉnh uj và đỉnh vj (các thay đổi trên không được áp dụng cho các truy vấn tiếp theo).
Bạn hãy ra tay giúp đỡ Dương làm chủ được cây Nhi nhé!
Input
Dòng đầu chứa hai số nguyên dương N và Q (2≤N≤10^5, 1≤Q≤10^5).
Dòng thứ i trong N−1 dòng tiếp theo chứa bốn số nguyên ui, vi, ci và di.
Dòng thứ j trong Q dòng tiếp theo chứa bốn số nguyên xj, yj, uj và vj.
Ouput
In ra Q dòng là câu trả lời cho các truy vấn tương ứng.
Ví dụ
Sample input 1
5 3
1 2 1 10
1 3 2 20
2 4 4 30
5 2 1 40
1 100 1 4
1 100 1 5
3 1000 3 4
Sample output 1
130
200
60