Double Tree
Contest: Educational Codeforces Round 62 (Rated for Div. 2)
Difficulty rating: 2700
Tags: data structures, divide and conquer, shortest paths, trees

You are given a special undirected graph. It consists of $$$2n$$$ vertices numbered from $$$1$$$ to $$$2n$$$. The following properties hold for the graph:

- there are exactly $$$3n-2$$$ edges in the graph: $$$n$$$ edges connect vertices having odd numbers with vertices having even numbers, $$$n - 1$$$ edges connect vertices having odd numbers with each other, and $$$n - 1$$$ edges connect vertices having even numbers with each other;
- for each edge $$$(u, v)$$$ between a pair of vertices with odd numbers, there exists an edge $$$(u + 1, v + 1)$$$, and vice versa;
- for each odd number $$$u \in [1, 2n - 1]$$$, there exists an edge $$$(u, u + 1)$$$;
- the graph is connected; moreover, if we delete all vertices with even numbers from it, and all edges incident to them, the graph will become a tree (the same applies to deleting odd vertices).

So, the graph can be represented as two trees having the same structure, and $$$n$$$ edges connecting each vertex of the first tree to the corresponding vertex of the second tree.

Edges of the graph are weighted. The length of some simple path in the graph is the sum of weights of traversed edges.

You are given $$$q$$$ queries to this graph; in each query, you are asked to compute the length of the shortest path between some pair of vertices in this graph. Can you answer all of the queries?

Input format:
The first line of the input contains one integer $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$w_{1, 2}$$$, $$$w_{3,4}$$$, ..., $$$w_{2n - 1, 2n}$$$ ($$$1 \le w_{i, i + 1} \le 10^{12}$$$). These integers describe the weights of the edges connecting odd vertices with even ones.

Then $$$n-1$$$ lines follow. $$$i$$$-th line contains four integers $$$x_i$$$, $$$y_i$$$, $$$w_{i, 1}$$$ and $$$w_{i, 2}$$$ ($$$1 \le x_i, y_i \le n$$$, $$$x_i \ne y_i$$$, $$$1 \le w_{i, j} \le 10^{12}$$$); it describes two edges: one connecting $$$2x_i - 1$$$ with $$$2y_i - 1$$$ and having weight $$$w_{i, 1}$$$; another connecting $$$2x_i$$$ with $$$2y_i$$$ and having weight $$$w_{i, 2}$$$.

The next line contains one integer $$$q$$$ ($$$1 \le q \le 6 \cdot 10^5$$$) — the number of queries.

Then $$$q$$$ lines follow, $$$i$$$-th line contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le 2n$$$, $$$u_i \ne v_i$$$), describing a query "compute the length of the shortest path between vertices $$$u_i$$$ and $$$v_i$$$".

Output format:
Print $$$q$$$ integers, $$$i$$$-th integer should be equal to the answer to the $$$i$$$-th query.

Constraints:
Time limit: 10.0 s
Memory limit: 1024.0 MB

Note:
The graph in the first test looks like that:

Example input:
5
3 6 15 4 8
1 2 5 4
2 3 5 7
1 4 1 5
1 5 2 1
3
1 2
5 6
1 10

Example output:
3
15
4

Editorial:
Suppose we want to minimize the number of traversed edges of the second type (edges that connect odd vertices to each other or even vertices to each other), and minimizing the length of the path has lower priority. Then we exactly know the number of edges of the second type we will use to get from one vertex to another; and when building a path, we each time either jump from one "tree" to another using an edge of the first type, or use the only edge of the second type that brings us closer to the vertex we want to reach. So, in this case problem can be solved either by binary lifting or by centroid decomposition. The model solution uses the latter: merge the graph into one tree (vertices $$$2i - 1$$$ and $$$2i$$$ of the original graph merge into vertex $$$i$$$ in the tree), build its centroid decomposition, and for each centroid $$$c$$$ and vertex $$$v$$$ of its centroid-subtree calculate the length of the shortest path from $$$2c - 1$$$ and $$$2c$$$ to $$$2v - 1$$$ and $$$2v$$$ using dynamic programming. Then the answer for each pair of vertices $$$u$$$ and $$$v$$$ may be calculated as follows: find the deepest centroid $$$c$$$ controlling the both vertices, and try either shortest path $$$u \rightarrow 2c - 1 \rightarrow v$$$ or shortest path $$$u \rightarrow 2c \rightarrow v$$$.
But this solution won't work in the original problem because sometimes we want to choose an edge of the second type that leads us further from the vertex we want to reach in the merged tree, but allows us to use a cheaper edge of the first type to jump from one tree to another. Let's make this situation impossible! We may change the weights of all edges of the second type so that the weight of edge between $$$2i - 1$$$ and $$$2i$$$ becomes the length of the shortest path between $$$2i - 1$$$ and $$$2i$$$. This can be done by solving a SSSP problem: build a graph of $$$n + 1$$$ vertices, where each vertex $$$i$$$ from $$$1$$$ to $$$n$$$ represents the path between from $$$2i - 1$$$ and $$$2i$$$. Add a directed edge with weight equal to $$$w_{2i - 1, 2i}$$$ going from vertex $$$0$$$ to vertex $$$i$$$. And finally, for every pair $$$i, j$$$ such that $$$2i - 1$$$ and $$$2j - 1$$$ are connected by edge of weight $$$w_1$$$, and $$$2i$$$ and $$$2j$$$ are connected by edge of weight $$$w_2$$$, add an undirected edge connecting $$$i$$$ and $$$j$$$ in the new graph (its weight should be $$$w_1 + w_2$$$). Then the distance from $$$0$$$ to $$$i$$$ in this graph will be equal to the length of the shortest path from $$$2i - 1$$$ to $$$2i$$$ in the original graph.