然而第六章的 A 面并没有草莓 - 题目 - HelloWorld信息学奥赛题库

题目描述

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 在关键点 $u_1$，而小 B 在关键点 $v_1$。为了能够战胜小 B，小 M 需要从她当前所在的关键点前往小 B 所在的关键点。然后小 B 会将小 M 反弹到关键点 $u_2$，而她自己瞬移到关键点 $v_2$，小 M 需要再从 $u_2$ 前往 $v_2$。这样的过程会重复 $q$ 次。形式化地说，小 M 需要做出 $q$ 次行动，每次行动给出一对 $\left<u_i,v_i\right>$，小 M 需要从关键点 $u_i$ 前往关键点 $v_i$。

每个关键点内都包含一定数量的草莓，更具体地，第 $i$ 个关键点内包含 $a_i$ 个草莓。小 M 想要在一次行动中收集尽量多的草莓，小 M 每经过一个关键点 $x$，她就能收集这个关键点内包含的所有 $a_x$ 个草莓，但是在同一次行动中，每个关键点内的草莓不能重复被收集。

每次小 M 能够前往与当前所在的关键点直接相连的关键点，但是她的移动十分危险，对于直接相连的一对关键点 $x\leftrightarrow y$，从 $x$ 到 $y$ 和从 $y$ 到 $x$ 有着各自的危险程度。一次行动的总危险程度定义为每次移动的危险程度的和，注意重复或反向的移动均算多次。

小 M 认为一次行动的收益为收集到的草莓的数量减去总危险程度，她想要你帮忙计算每次行动的最大收益。

输入格式

第一行两个正整数 $n,q$，意义见题目描述。

第二行一共 $n$ 个正整数，表示 $a_1,a_2,\ldots,a_n$。

接下来 $n-1$ 行，每行四个正整数 $x,y,z_1,z_2$ 表示关键点 $x$ 和 $y$ 直接相连，且从 $x$ 到 $y$ 的危险程度为 $z_1$，从 $y$ 到 $x$ 的危险程度为 $z_2$。

接下来 $q$ 行，第 $i$ 行两个正整数 $u_i,v_i$，表示第 $i$ 次行动的起点和终点。

输出格式

输出 $q$ 行，第 $i$ 行包含一个整数，表示第 $i$ 次行动的最大收益。

样例 1

input

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

output

每次行动的最优行动方式之一如下：

$(1,1)$：$1\to2\to4\to5\to4\to2\to3\to2\to1$。

其收益的计算方式为：

收集到的草莓的数量为 $a_1+a_2+a_3+a_4+a_5=21$。

总危险程度为 $3+1+1+1+1+2+2+1=12$。

收益为 $21-12=9$。

$(4,4)$：$4\to2\to1\to2\to3\to2\to4$。

$(5,6)$：$5\to4\to2\to3\to2\to1\to2\to4\to6$。

$(6,4)$：$6\to4\to2\to1\to2\to3\to2\to4$。

$(3,4)$：$3\to2\to1\to2\to4$。

$(3,7)$：$3\to2\to1\to2\to4\to5\to4\to2\to3\to7$。

$(5,1)$：$5\to4\to2\to3\to2\to1$。

$(4,7)$：$4\to5\to4\to2\to1\to2\to3\to7$。

$(7,1)$：$7\to3\to2\to4\to2\to1$。

样例 2

input

output

见选手目录下的 strawberry2.in 与 strawberry2.ans。

数据范围与提示

对于所有测试点：

$1\le n\le2\times10^5$，$1\le q\le5\times10^5$

$1\le x,y,u_i,v_i\le n$，$x\ne y$，$1\le a_i,z_1,z_2\le10^4$

保证任意两个关键点之间有且仅有一条不重复经过关键点的路径。

每个测试点的具体限制见下表：

测试点编号	$n\le$	$q\le$	特殊性质
$1\sim2$	$10$	$10$	无
$3\sim4$	$1000$	$1000$	A
$5\sim6$	$1000$	$1000$	B
$7\sim8$	$1000$	$1000$	无
$9\sim10$	$2\times10^5$	$1$	A
$11\sim12$	$1000$	$5\times10^5$	无
$13\sim14$	$2\times10^5$	$5\times10^5$	A
$15\sim16$	$2\times10^5$	$5\times10^5$	B
$17\sim20$	$2\times10^5$	$5\times10^5$	无

特殊性质 A：$y = x + 1$。

特殊性质 B：$x = 1$。

Author: PinkRabbit

HelloWorld信息学奥赛题库