CF1140G.Double Tree

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?

你被给定一个特殊的无向图。该图包含 $2n$ 个顶点，编号从 $1$ 到 $2n$。该图满足以下性质：

• 图中恰好有 $3n-2$ 条边：其中 $n$ 条边连接奇数编号顶点与偶数编号顶点，$n - 1$ 条边连接奇数编号顶点彼此之间，另外 $n - 1$ 条边连接偶数编号顶点彼此之间；
• 对于任意一条连接两个奇数编号顶点 $u$ 与 $v$ 的边 $(u, v)$，图中必存在边 $(u + 1, v + 1)$，反之亦然；
• 对每个奇数 $u \in [1, 2n - 1]$，图中均存在边 $(u, u + 1)$；
• 图是连通的；此外，若删除图中所有偶数编号顶点及其所有关联边，则剩余部分构成一棵树（对奇数编号顶点做同样操作，剩余部分也是一棵树）。

因此，该图可表示为两棵结构完全相同的树，外加 $n$ 条边，每条边连接第一棵树中的某个顶点与其在第二棵树中对应的顶点。

图中的边均带有权重。某条简单路径的长度定义为该路径上所有经过边的权重之和。

你将收到关于该图的 $q$ 个查询；对每个查询，你需要计算图中某一对顶点之间的最短路径长度。你能回答所有这些查询吗？

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$".

输入的第一行包含一个整数 $n$（$2 \le n \le 3 \cdot 10^5$）。

第二行包含 $n$ 个整数 $w_{1, 2}$、$w_{3,4}$、…、$w_{2n - 1, 2n}$（$1 \le w_{i, i + 1} \le 10^{12}$）。这些整数表示连接奇数编号顶点与偶数编号顶点的边的权重。

接下来是 $n-1$ 行。第 $i$ 行包含四个整数 $x_i$、$y_i$、$w_{i, 1}$ 和 $w_{i, 2}$（$1 \le x_i, y_i \le n$，$x_i \ne y_i$，$1 \le w_{i, j} \le 10^{12}$）；它描述两条边：一条连接顶点 $2x_i - 1$ 与 $2y_i - 1$，权重为 $w_{i, 1}$；另一条连接顶点 $2x_i$ 与 $2y_i$，权重为 $w_{i, 2}$。

下一行包含一个整数 $q$（$1 \le q \le 6 \cdot 10^5$）—— 查询的数量。

随后是 $q$ 行，第 $i$ 行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le 2n$，$u_i \ne v_i$），表示一个查询：“计算顶点 $u_i$ 与 $v_i$ 之间最短路径的长度”。

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

输出 $q$ 个整数，其中第 $i$ 个整数应等于第 $i$ 个查询的答案。

The graph in the first test looks like that:

第一个测试用例中的图如下所示：