#P5024. [NOIP2018 提高组] 保卫王国

    ID: 1946 Type: Default 1000ms 256MiB Tried: 2 Accepted: 1 Difficulty: 10 Uploaded By: Tags>动态规划,dp2018倍增NOIp 提高组树链剖分

[NOIP2018 提高组] 保卫王国

题目背景

NOIP2018 提高组 D2T3

题目描述

Z 国有 nn 座城市,(n1)(n - 1) 条双向道路,每条双向道路连接两座城市,且任意两座城市都能通过若干条道路相互到达。

Z 国的国防部长小 Z 要在城市中驻扎军队。驻扎军队需要满足如下几个条件:

  • 一座城市可以驻扎一支军队,也可以不驻扎军队。
  • 由道路直接连接的两座城市中至少要有一座城市驻扎军队。
  • 在城市里驻扎军队会产生花费,在编号为 ii 的城市中驻扎军队的花费是 pip_i

小 Z 很快就规划出了一种驻扎军队的方案,使总花费最小。但是国王又给小 Z 提出了 mm 个要求,每个要求规定了其中两座城市是否驻扎军队。小 Z 需要针对每个要求逐一给出回答。具体而言,如果国王提出的第 jj 个要求能够满足上述驻扎条件(不需要考虑第 jj 个要求之外的其它要求),则需要给出在此要求前提下驻扎军队的最小开销。如果国王提出的第 jj 个要求无法满足,则需要输出 1-1。现在请你来帮助小 Z。

输入格式

第一行有两个整数和一个字符串,依次表示城市数 nn,要求数 mm 和数据类型 typetypetypetype 是一个由大写字母 ABC 和一个数字 123 组成的字符串。它可以帮助你获得部分分。你可能不需要用到这个参数。这个参数的含义在【数据规模与约定】中 有具体的描述。

第二行有 nn 个整数,第 ii 个整数表示编号 ii 的城市中驻扎军队的花费 pip_i

接下来 (n1)(n - 1) 行,每行两个整数 u,vu,v,表示有一条 uuvv 的双向道路。

接下来 mm 行,每行四个整数 a,x,b,ya, x, b, y,表示一个要求是在城市 aa 驻扎 xx 支军队,在城市 bb 驻扎 yy 支军队。其中,x,yx,y 的取值只有 0011

  • xx00,表示城市 aa 不得驻扎军队。
  • xx11,表示城市 aa 必须驻扎军队。
  • yy00,表示城市 bb 不得驻扎军队。
  • yy11,表示城市 bb 必须驻扎军队。

输入文件中每一行相邻的两个数据之间均用一个空格分隔。

输出格式

输出共 mm 行,每行包含一个个整数,第 jj 行表示在满足国王第 jj 个要求时的最小开销, 如果无法满足国王的第 jj 个要求,则该行输出 1-1

5 3 C3 
2 4 1 3 9 
1 5 
5 2 
5 3 
3 4 
1 0 3 0 
2 1 3 1 
1 0 5 0

12 
7 
-1

提示

样例 1 解释

  • 对于第一个要求,在 44 号和 55 号城市驻扎军队时开销最小。
  • 对于第二个要求,在 11 号、22 号、33 号城市驻扎军队时开销最小。
  • 第三个要求是无法满足的,因为在 11 号、55 号城市都不驻扎军队就意味着由道路直接连 接的两座城市中都没有驻扎军队。

数据规模与约定

测试点编号 type\text{type} n=m=n = m=
1,21,2 A3 1010
3,43,4 C3
5,65,6 A3 100100
77 C3
8,98,9 A3 2×1032\times 10^3
10,1110,11 C3
12,1312,13 A1 10510^5
14,15,1614, 15, 16 A2
1717 A3
18,1918,19 B1
20,2120,21 C1
2222 C2
23,24,2523, 24, 25 C3

数据类型的含义:

  • A:城市ii与城市i+1i + 1直接相连。
  • B:任意城市与城市 11 的距离不超过 100100(距离定义为最短路径上边的数量),即如果这 棵树以 11 号城市为根,深度不超过 100100
  • C:在树的形态上无特殊约束。
  • 1:询问时保证a=1,x=1a = 1,x = 1,即要求在城市 11 驻军。对b,y没有限制。
  • 2:询问时保证a,ba,b是相邻的(由一条道路直接连通)
  • 3:在询问上无特殊约束。

对于 100%100\%的数据,保证 1n,m1051 \leq n,m ≤ 10^51pi1051 ≤ p_i ≤ 10^51u,v,a,bn1 \leq u, v, a, b \leq naba \neq bx,y{0,1}x, y \in \{0, 1\}