【拾题杂谈】LuoguP5024 保卫王国
题面
题目描述
Z 国有 $n$ 座城市,$(n - 1)$ 条双向道路,每条双向道路连接两座城市,且任意两座城市都能通过若干条道路相互到达。
Z 国的国防部长小 Z 要在城市中驻扎军队。驻扎军队需要满足如下几个条件:
- 一座城市可以驻扎一支军队,也可以不驻扎军队。
- 由道路直接连接的两座城市中至少要有一座城市驻扎军队。
- 在城市里驻扎军队会产生花费,在编号为 $i$ 的城市中驻扎军队的花费是 $p_i$。
小 Z 很快就规划出了一种驻扎军队的方案,使总花费最小。但是国王又给小 Z 提出了 $m$ 个要求,每个要求规定了其中两座城市是否驻扎军队。小 Z 需要针对每个要求逐一给出回答。具体而言,如果国王提出的第 $j$ 个要求能够满足上述驻扎条件(不需要考虑第 $j$ 个要求之外的其它要求),则需要给出在此要求前提下驻扎军队的最小开销。如果国王提出的第 $j$ 个要求无法满足,则需要输出 $-1$。现在请你来帮助小 Z。
输入格式
第一行有两个整数和一个字符串,依次表示城市数 $n$,要求数 $m$ 和数据类型 $type$。$type$ 是一个由大写字母 A
,B
或 C
和一个数字 1
,2
,3
组成的字符串。它可以帮助你获得部分分。你可能不需要用到这个参数。这个参数的含义在【数据规模与约定】中 有具体的描述。
第二行有 $n$ 个整数,第 $i$ 个整数表示编号 $i$ 的城市中驻扎军队的花费 $p_i$。
接下来 $(n - 1)$ 行,每行两个整数 $u,v$,表示有一条 $u$ 到 $v$ 的双向道路。
接下来 $m$ 行,每行四个整数 $a, x, b, y$,表示一个要求是在城市 $a$ 驻扎 $x$ 支军队,在城市 $b$ 驻扎 $y$ 支军队。其中,$x,y$ 的取值只有 $0$ 或 $1$:
- 若 $x$ 为 $0$,表示城市 $a$ 不得驻扎军队。
- 若 $x$ 为 $1$,表示城市 $a$ 必须驻扎军队。
- 若 $y$ 为 $0$,表示城市 $b$ 不得驻扎军队。
- 若 $y$ 为 $1$,表示城市 $b$ 必须驻扎军队。
输入文件中每一行相邻的两个数据之间均用一个空格分隔。
输出格式
输出共 $m$ 行,每行包含一个个整数,第 $j$ 行表示在满足国王第 $j$ 个要求时的最小开销, 如果无法满足国王的第 $j$ 个要求,则该行输出 $-1$。
样例 #1
样例输入 #1
1 | 5 3 C3 |
样例输出 #1
1 | 12 |
提示
样例 1 解释
- 对于第一个要求,在 $4$ 号和 $5$ 号城市驻扎军队时开销最小。
- 对于第二个要求,在 $1$ 号、$2$ 号、$3$ 号城市驻扎军队时开销最小。
- 第三个要求是无法满足的,因为在 $1$ 号、$5$ 号城市都不驻扎军队就意味着由道路直接连 接的两座城市中都没有驻扎军队。
数据规模与约定
测试点编号 | $\text{type}$ | $n = m=$ |
---|---|---|
$1,2$ | A3 |
$10$ |
$3,4$ | C3 |
$10$ |
$5,6$ | A3 |
$100$ |
$7$ | C3 |
$100$ |
$8,9$ | A3 |
$2\times 10^3$ |
$10,11$ | C3 |
$2\times 10^3$ |
$12,13$ | A1 |
$10^5$ |
$14, 15, 16$ | A2 |
$10^5$ |
$17$ | A3 |
$10^5$ |
$18,19$ | B1 |
$10^5$ |
$20,21$ | C1 |
$10^5$ |
$22$ | C2 |
$10^5$ |
$23, 24, 25$ | C3 |
$10^5$ |
数据类型的含义:
A
:城市 $i$ 与城市 $i + 1$ 直接相连。B
:任意城市与城市 $1$ 的距离不超过 $100$(距离定义为最短路径上边的数量),即如果这 棵树以 $1$ 号城市为根,深度不超过 $100$。C
:在树的形态上无特殊约束。1
:询问时保证 $a = 1,x = 1$,即要求在城市 $1$ 驻军。对 $b,y$ 没有限制。2
:询问时保证 $a,b$ 是相邻的(由一条道路直接连通)3
:在询问上无特殊约束。
对于 $100%$的数据,保证 $1 \leq n,m ≤ 10^5$,$1 ≤ p_i ≤ 10^5$,$1 \leq u, v, a, b \leq n$,$a \neq b$,$x, y \in {0, 1}$。
思路
思维初探:暴力做法
对于前 11 个数据点,$n,m$ 都特别小,我们完全可以对于每一个询问做一次 DP 。
不妨设置 $dp[i][0/1]$ 表示这个点选 ( 1 ) 或者不选 ( 0 ) 的价值。那么不难想到转移方程式子:
$$
dp[u][0] = \sum\limits_{v ∈ son[u]}p[v][1]\
dp[u][1] = \sum\limits_{v ∈ son[u]}\min\left(dp[v][0] ,dp[v][1]\right) + a[u]
$$
如果想要一个节点选或者不选,只需要让他的权值变成 0 或者 极大值即可。
1 | namespace Sub1 { |
侧面突破:链上做法
观察数据点,有 $24\ \tt pts$ 的链上做法。我们考虑链上的做法,其实链就是一个区间,所以说链上的做法就不难想到线段树。我们定义线段树上的一个节点存储一个矩阵:
$$
\left[\begin{matrix}
(0,0)&(0,1)\
(1,0)&(1,1)
\end{matrix}\right]
$$
这个矩阵每一个元素表示当前结点的左端点(第一个元素)取(1)或者不取(0)、右端点(第二个元素)取(1)或者不取(0)的最小值。
合并的时候分别讨论即可。
正解思路:倍增合并
我们发现,如果要从链进化成树,可以用倍增的思想变成一段一段的然后合并,这时倍增维护的东西应当是和线段树一样的,然后我们考虑如何计算答案。
首先基础的,我们需要两个数组 $f[i][0/1]$ 和 $g[i][0/1]$ 分别表示当前这个点选或者不选这个点的子树的最小方案、还有这棵树挖掉以这个点为子树之后这个点选不选的最小方案。
我们设定数组 $dp[i][j][0/1][0/1]$ 表示:节点 $i$ 到节点 $i$ 的 $2^j$ 个祖先的路径上,$i$ 节点选或不选(1/0)$i$ 节点的 $2^j$ 个父亲选或不选的最小方案
然后有了这些数组我们就可以处理询问了。
- 如果 $a$ 是 $b$ 的祖先,那么可以直接倍增上去(还是像 $dp$ 一样合并倍增数组,枚举中间点的状态即可),然后不要忘了加上 $g[a][x]$ 。
- 否则我们需要先把 $a$ 和 $b$ 都倍增到 $lca$ 的儿子处,然后枚举 $lca$ 和两个儿子的状态,具体可以见代码。
1 | // #pragma GCC optimize(2) |