P8820 数据传输 transmit 题解

· · 个人记录

想出来再厉害的做法，你调不出来也是假的。

写一下题解，顺便纪念一下考场上少加一个等号挂 100 分的事实。

比今年简单的 csps 不多了……希望 noip 不要寄成这个狗样。

如果说错了请线下打我。

考虑搬到序列上的做法，即给你 w_1,w_2,...,w_n，求 (l,r) 中取若干数，构造序列 p_1=l,p_m=r,\forall i \in (2,m],p_i-p_{i-1}\le k，使得 \sum\limits_{i=1}^{m}w_{p_i} 最小。

可以直接设 dp_i 表示到 i 点的最小答案，显然有 dp_i\gets \min\limits_{d=1}^{k}\{dp_{i-d}\}+w_i。

这东西能用广义矩阵乘法优化，假如 k=3：

[dp_{i-1},dp_{i-2},dp_{i-3}]\begin{bmatrix}w_i&0&∞\\w_i&∞&0\\w_i&∞&∞\end{bmatrix}=[dp_{i},dp_{i-1},dp_{i-2}]

然后你把这直接搬到树上，大概可以获得 60 分（过掉 k=1,2 ）的点。

显然这个东西是能过 k=1 的，由于 k=2 的情况时没有从 v 跳到 u 子树再跳回来的情况（因为这样还不如直接跳 u ……），所以直接拿线段树/倍增维护上述转移矩阵应该都是可行的。

但是 k=3 时，考虑从 v 跳到 u 或 u 的上面，有两种可能：

你把上面那个 dp 糊了上去，过不了官方给的大样例。

那我们重新定义 dp 状态：dp_{u,0/1/2} 表示跑到 u 的子树内距离 u 点为 0/1/2 的最小答案。

那么有下述转移（记 v 为 u 的儿子，N(u) 为 u 的邻域即 \bigcup\{t|(u,t)\in E\}）：

上述转移有一个重点：深度大的都不可能从深度小的转移过来，感性理解，因为如果你跳回去了，你必定走反方向，而这样必定不优。

可以预处理 mn_u=\min\limits_{t\in N(i)}w_t，然后写成矩阵形式：

[dp_{v,0},dp_{v,1},dp_{v,2}]\begin{bmatrix}w_u&0&∞\\w_u&mn_u&0\\w_u&∞&∞\end{bmatrix}=[dp_{u,0},dp_{u,1},dp_{u,2}]

其实只改了一个元素。

对于询问 (u,v)，让 u 为深度较大的那个点，然后钦定一开始选 u，把答案矩阵赋为 [w_u,∞,∞]，然后求 fa_u 到 v 上的矩阵积即可。

代码，使用树剖加线段树维护矩阵，通过了洛谷的民间数据和 infOJ 的数据，复杂度 O(q\log^2 n)。