← 返回题目列表

Codeforces · 1140/G

G. 双树

中文机器翻译题面 查看原题

给你一个特殊的无向图。它由 $$$2n$$$ 个顶点组成,编号从 $$$1$$$ 到 $$$2n$$$。该图具有以下属性:

- 图中正好有 $$$3n-2$$$ 边:$$$n$$$ 边将奇数编号的顶点与偶数编号的顶点连接起来,$$$n - 1$$$ 边将奇数编号的顶点彼此连接,$$$n - 1$$$ 边将偶数编号的顶点彼此连接;
- 对于一对奇数顶点之间的每条边 $$$(u, v)$$$,都存在一条边 $$$(u + 1, v + 1)$$$,反之亦然;
- 对于 [1, 2n - 1]$$$ 中的每个奇数 $$$u \,存在一条边 $$$(u, u + 1)$$$;
- 图已连接;此外,如果我们删除其中所有偶数的顶点,以及所有与它们相关的边,该图将成为一棵树(同样适用于删除奇数顶点)。

因此,图可以表示为具有相同结构的两棵树,以及将第一棵树的每个顶点连接到第二棵树的相应顶点的$$$n$$$条边。

图形的边缘被加权。图中某些简单路径的长度是遍历边的权重之和。

您将收到对此图表的 $$$q$$$ 查询;在每个查询中,系统都会要求您计算该图中某对顶点之间的最短路径的长度。您能回答所有问题吗?

输入

输入的第一行包含一个整数 $$$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$$$"。

输出

打印 $$$q$$$ 整数,第 $$$i$$$ 个整数应等于第 $$$i$$$ 个查询的答案。

示例

输入 #1

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

输出 #1

3
15
4

注意

第一个测试中的图表如下所示: