405185: GYM101810 M Greedy Pirate

You are given n islands numbered from 1 to n and connected using n - 1 magical bridges. A greedy pirate wants to collect as many coins as possible by traveling through the bridges. Each bridge is a two-way bridge, but the pirate can only use the bridge at most twice. If a bridge connects islands u and v, then going from u to v gives c₁ coins, and going from v to u gives c₂.

Help the pirate to collect as many coins as he can knowing that he will start from some island x and finish at some island y.

The first line contains an integer T (1 ≤ T ≤ 100) specifying the number of test cases.

The first line of each test case contains one integer n (2 ≤ n ≤ 10⁵), in which n is the number of islands. The n - 1 lines follow, giving the bridges. Each line contains four integers u, v, c₁, and c₂ (1 ≤ u, v ≤ n, 1 ≤ c₁, c₂ ≤ 10⁴), as describing in the statement above.

The next line contains an integer q (1 ≤ q ≤ 10⁵), in which q is the number of queries. Then q lines follow, giving queries. Each query consists of two integers x and y (1 ≤ x, y ≤ n), in which x and y are the starting and finish islands, respectively.

The sum of n and q overall test cases does not exceed 25 × 10⁵ for each.

For each query, print a single line containing the maximum amount of money the greedy pirate can collect by traveling through the bridges starting from island x and finishing at island y.

1
5
1 2 5 10
3 5 25 3
4 2 15 12
3 2 6 7
2
1 5
4 3

64
65