题目描述
Source: Educational Codeforces Round 46 (Rated for Div. 2) G. Two-Paths
从危险的神庙中逃离后，Madeline 与 Theo 在悬崖边点燃了篝火准备休息。但当 Madeline 从噩梦中惊醒时，她发现自己的半个身子已经滑落了悬崖的边缘。当 Theo 慌忙起身时，Madeline 已从悬崖边坠落……
在 Celeste 山上，会发生许多不可思议的事情。当 Madeline（以下简称小 M）再一次醒来时，她发现自己身处地下深处，而 Badeline ——她的负面情绪的化身（以下简称小 B）则幽异地飘在空中，对她露出不祥的笑容。
小 M 发现她所处的区域可以抽象成一个含有 n 个关键点的图，且有 n−1 对关键点之间直接相连，满足任意两个关键点之间有且仅有一条不重复经过关键点的路径。
初始时小 M 在关键点 u1，而小 B 在关键点 v1。为了能够战胜小 B，小 M 需要从她当前所在的关键点前往小 B 所在的关键点。然后小 B 会将小 M 反弹到关键点 u2，而她自己瞬移到关键点 v2，小 M 需要再从 u2 前往 v2。这样的过程会重复 q 次。形式化地说，小 M 需要做出 q 次行动，每次行动给出一对 ⟨ui,vi⟩，小 M 需要从关键点 ui 前往关键点 vi。
每个关键点内都包含一定数量的草莓，更具体地，第 i 个关键点内包含 ai 个草莓。小 M 想要在一次行动中收集尽量多的草莓，小 M 每经过一个关键点 x，她就能收集这个关键点内包含的所有 ax 个草莓，但是在同一次行动中，每个关键点内的草莓不能重复被收集。
每次小 M 能够前往与当前所在的关键点直接相连的关键点，但是她的移动十分危险，对于直接相连的一对关键点 x↔y，从 x 到 y 和从 y 到 x 有着各自的危险程度。一次行动的总危险程度定义为每次移动的危险程度的和，注意重复或反向的移动均算多次。
小 M 认为一次行动的收益为收集到的草莓的数量减去总危险程度，她想要你帮忙计算每次行动的最大收益。
输入格式
第一行两个正整数 n,q，意义见题目描述。
第二行一共 n 个正整数，表示 a1,a2,…,an。
接下来 n−1 行，每行四个正整数 x,y,z1,z2 表示关键点 x 和 y 直接相连，且从 x 到 y 的危险程度为 z1，从 y 到 x 的危险程度为 z2。
接下来 q 行，第 i 行两个正整数 ui,vi，表示第 i 次行动的起点和终点。
输出格式
输出 q 行，第 i 行包含一个整数，表示第 i 次行动的最大收益。
样例 1
7 9
6 5 5 3 2 1 2
1 2 3 1
2 3 2 2
2 4 1 1
4 5 1 1
6 4 1 3
7 3 12 14
1 1
4 4
5 6
6 4
3 4
3 7
5 1
4 7
7 1
9
9
8
9
12
-3
14
0
4
每次行动的最优行动方式之一如下：
(1,1)：1→2→4→5→4→2→3→2→1。
其收益的计算方式为：
收集到的草莓的数量为 a1+a2+a3+a4+a5=21。
总危险程度为 3+1+1+1+1+2+2+1=12。
收益为 21−12=9。
(4,4)：4→2→1→2→3→2→4。
(5,6)：5→4→2→3→2→1→2→4→6。
(6,4)：6→4→2→1→2→3→2→4。
(3,4)：3→2→1→2→4。
(3,7)：3→2→1→2→4→5→4→2→3→7。
(5,1)：5→4→2→3→2→1。
(4,7)：4→5→4→2→1→2→3→7。
(7,1)：7→3→2→4→2→1。
样例 2
见选手目录下的 strawberry2.in 与 strawberry2.ans。
数据范围与提示
对于所有测试点：
1≤n≤2×105，1≤q≤5×105
1≤x,y,ui,vi≤n，x=y，1≤ai,z1,z2≤104
保证任意两个关键点之间有且仅有一条不重复经过关键点的路径。
每个测试点的具体限制见下表：
| 测试点编号 |
n≤ |
q≤ |
特殊性质 |
| 1∼2 |
10 |
无 |
| 3∼4 |
1000 |
A |
| 5∼6 |
B |
| 7∼8 |
无 |
| 9∼10 |
2×105 |
1 |
A |
| 11∼12 |
1000 |
5×105 |
无 |
| 13∼14 |
2×105 |
A |
| 15∼16 |
B |
| 17∼20 |
无 |
特殊性质 A：y=x+1。
特殊性质 B：x=1。
Author: PinkRabbit
