Bài G - Educatioal Round 62

Đề bài:
Bạn được cho 1 đồ thị vô hướng đặc biệt. Nó bao gồm $2n$ đỉnh được đánh số từ 1 đến 2n. Dưới đây là một số đặc tính của đồ thị:
+ Có chính xác 3n-2 cạnh trong đồ thị: n cạnh kết nối các đỉnh với số lẻ với các đỉnh có số chẵn, n-1 cạnh kết nối các đỉnh với số lẻ với nhau và n-1 cạnh kết nối các đỉnh có số chẵn với nhau.
+ Với mỗi cạnh (u,v) giữa 1 cặp các đỉnh với số lẻ, tồn tại 1 cạnh (u+1,v+1) và  ngược lại.
+ Với mỗi số lẻ u thuộc [1,2n-1], tồn tại 1 cạnh (u,u+1);
 + Đồ thi là liên thông, hơn thế nữa, nếu ta xóa tất cả các đỉnh với số lượng chẵn từ nó, và tất cả các cạnh kể với nó, đồ thị sẽ trở thành 1 cây (tương tự cho việc xóa các đỉnh lẻ).
 Vì vậy, đồ thị có thể được biểu diễn như hai cây có cùng cấu trúc, và n cạnh kết nỗi với mỗi đỉnh của cây đầu tiên tương ứng với cây thứ hai.
Các cạnh của đồ thị đều có trọng lượng. Chiều dài của một vài đường đi đơntrong đồ thị là tổng các trọng lượng của các cạnh được duyệt qua.
Đầu vào:
+ Dòng đầu tiên của đầu vào chứa 1 số nguyên n (2<=n<=3.10^5).
+ Dòng thứ 2 chứa n số nguyên $w(1,2),w(3,4),...,w(2n-1,2n)(1<=w(i,i+1)<=10^(12))$.
  Các số nguyên này mô tả trọng lượng của các cạnh kết nối với các đỉnh lẻ với đỉnh chẵn.
+n-1 dòng tiếp theo, dòng thứ i chứa 4 số nguyên x(i),y(i),w(i,1) và w(i,2).
(1<=x(i),y(i)<=n,x(i) # y(i),1<=w(i,j)<=10^(12)); nó môt tả hai cạnh;, một kết nối 2x(i)-1 với 2y(i)-1 và có trọng lượng w(i,1) ; mặt khác nối 2x(i) với 2y(i) và có trọng lương w(i,2).