【NOIP2018】保卫王国 排行榜
时间限制: 2 s
空间限制: 524288 KB
问题描述
Z国有 $n$ 座城市,$n-1$ 条双向道路,每条双向道路连接两座城市,且任意两座城市都能通过若干条道路相互到达。
Z国的国防部长小Z要在城市中驻扎军队。驻扎军队需要满足如下几个条件:
- 一座城市可以驻扎一支军队,也可以不驻扎军队。
- 由道路直接连接的两座城市中至少要有一座城市驻扎军队。
- 在城市里驻扎军队会产生花费,在编号为的城市中驻扎军队的花费是 $p_i$。
小Z很快就规划出了一种驻扎军队的方案,使总花费最小。但是国王又给小Z提出了 $m$ 个要求,每个要求规定了其中两座城市是否驻扎军队。小Z需要针对每个要求逐一给出回答。具体而言,如果国王提出的第个要求能够满足上述驻扎条件(不需要考虑第 $j$ 个要求之外的其它要求),则需要给出在此要求前提下驻扎军队的最小开销。如果国王提出的第 $j$ 个要求无法满足,则需要输出 $-1$ $(1 \le j \le m)$ 。现在请你来帮助小Z。
输入格式
从标准输入读入数据。
第 $1$ 行包含两个正整数 $n,m$ 和一个字符串 $type$,分别表示城市数、要求数和数据类型。$type$ 是一个由大写字母 A,B 或 C 和一个数字 1,2,3 组成的字符串。它可以帮助你获得部分分。你可能不需要用到这个参数。这个参数的含义在【数据规模与约定】中有具体的描述。
第 $2$ 行 $n$ 个整数 $p_i$,表示编号 $i$ 的城市中驻扎军队的花费。
接下来 $n-1$ 行,每行两个正整数 $u, v$,表示有一条 $u$ 到 $v$ 的双向道路。
接下来 $m$ 行,第 $j$ 行四个整数 $a,x,b,y ~ (a \ne b)$,表示第 $j$ 个要求是在城市 $a$ 驻扎 $x$ 支军队,在城市 $b$ 驻扎 $y$ 支军队。其中,$x$、$y$ 的取值只有 0 或 1 :若 $x$ 为 0,表示城市 $a$ 不得驻扎军队,若 $x$ 为 1,表示城市 $a$ 必须驻扎军队;若 $y$ 为 0,表示城市 $b$ 不得驻扎军队,若 $y$ 为 1,表示城市 $b$ 必须驻扎军队。
输入文件中每一行相邻的两个数据之间均用一个空格分隔。
输出格式
输出到标准输出。
输出共 $m$ 行,每行包含 1 个整数,第行表示在满足国王第 $j$ 个要求时的最小开销,如果无法满足国王的第 $j$ 个要求,则该行输出 -1。
样例输入
样例输出
样例解释
对于第一个要求,在 4 号和 5 号城市驻扎军队时开销最小。
对于第二个要求,在 1 号、2 号、3 号城市驻扎军队时开销最小。
第三个要求是无法满足的,因为在 1 号、5 号城市都不驻扎军队就意味着由道路直接连接的两座城市中都没有驻扎军队。
数据规模与约定
对于 100% 的数据,$n,m \le 100000, 1 \le p_i \le 100000$。
测试点编号 | $type$ | $n = $ | $m = $ |
---|---|---|---|
1 ~ 2 | A3 | $10$ | $10$ |
3 ~ 4 | C3 | ||
5 ~ 6 | A3 | $100$ | $100$ |
7 | C3 | ||
8 ~ 9 | A3 | $2000$ | $2000$ |
10 ~ 11 | C3 | ||
12 ~ 13 | A1 | $100000$ | $100000$ |
14 ~ 16 | A2 | ||
17 | A3 | ||
18 ~ 19 | B1 | ||
20 ~ 21 | C1 | ||
22 | C2 | ||
23 ~ 25 | C3 |
数据类型的含义:
A:城市 $i$ 与城市 $i+1$ 直接相连。
B:任意城市与城市 1 的距离不超过 100(距离定义为最短路径上边的数量),即如果这棵树以 1 号城市为根,深度不超过 100。
C:在树的形态上无特殊约束。
1:询问时保证 $a=1, x=1$,即要求在城市 1 驻军。对 $b,y$ 没有限制。
2:询问时保证 $a,b$ 是相邻的(由一条道路直接连通)
3:在询问上无特殊约束。
题目来源
NOIP 2018 Day 2
关于接口中的数组初值说明(最后更新:2023年2月6日)
若题目要求实现函数接口,且该函数中存在仅用于输出的数组(如 void solve(int n, const int *in, int *out)
中的 out
),那么除非另外说明,否则该数组在程序启动时的初值为 0
。
关于标准输出的说明(最后更新:2018年10月23日)
标准输出将被重定向到内存中,所以你的内存使用量也包括了你的标准输出的大小(向上取整到 4KB 的倍数)。
如果你的程序要进行大量输出,请考虑这一点。
关于提交的说明
你提交的代码将会被公开,所有人都可见。如果这不是你所期望的,或者如果想要删除已提交的代码,请联系管理员。
Judge Duck Online | 评测鸭在线
Server Time: 2024-12-04 11:54:34 | Loaded in 0 ms | Server Status
个人娱乐项目,仅供学习交流使用 | 捐赠