提示:我这个方法比其它解法还要麻烦,目前最简洁的解法是 dottle 的解法,推荐阅读,我仅在此说明我的思路。
给定 \(n\) 个点的树,点 \(i\) 的点权为 \(a_i\),给定整数 \(k\)。
称一条路径是合法的,当且仅当路径上相邻两点在树上的距离不超过 \(k\)。
定义一条路径的花费为路径上的点权之和。
\(m\) 次询问,每次给定 \(u,v\),求 \(u\to v\) 路径花费的最小值。
\(1\le n,m\le 2\times 10^5\)。
Preface
又是一年 CSP 啊,虽然比去年长进不少,可仔细看来变化还是不大,去年考场上看出了 T1 的做法却写不出来,今年面对 T4 亦是如此啊,从这道题学到了不少。
主要还是方法有点笨,以及写的过程中失误太多,考场下我花了将近 4h 才写完,在考场上根本没有这个时间。这说明考场上适当的决策也很重要。
此外,考场上我因为始终没有发现 \(k=3\) 时可以跳出链外,导致 \(k=3\) 样例一直过不去,而我一直没有发现这个问题,只是对着程序不断静态纠错,最后因为过于匆忙甚至 \(k=1\) 写挂,没删调试都没发现,最后原地爆炸。
还是要调整好心态,不管什么时候都要保持冷静。
Analysis
首先,看到 \(k\le 3\) 的范围,显然是要分类讨论。
k=1:
显然,最小花费即为 \(u\to v\) 在树上路径的点权和。倍增预处理,每次查询 LCA 然后树上前缀和即可。
时间复杂度 \(\mathcal O((n+m)\log n)\)。
k=2:
先考虑暴力的做法。将 \(u\to v\) 在树上的路径拆下来,将点权写作序列 \(b_{1\sim p}\) 研究。
我们用动态规划解决这个问题。设 \(f(i)\) 表示 \(1\sim i\) 的最小花费。
初始状态:\(f(1)=b_1\)。
状态转移方程:\(f(i)=\min\{f(i-1)+b_i,f(i-2)+b_i\}\)。
如果对矩阵很熟悉,不难发现这个就是一个矩阵优化的板子。
不过此处 \(b_i\) 是变量,无法进行矩阵快速幂,当时考场上想到这里我脑子莫名其妙宕机了,感觉这题正解绝对是矩阵,但这个东西不会处理啊,然后就彻底蒙了,完全想偏了,最后打了暴力。
实际上和快速幂没有任何关系。因为是树上的静态查询问题,自然可以往倍增想。
因为矩阵满足交换律和结合律,完全可以把矩阵先存起来预处理,最后查询的时候再一次倍增求解。
先把上面那个式子写成矩阵:
\[\begin{bmatrix} f(i-1) & f(i-2) \end{bmatrix} \times \begin{bmatrix} a_i & 0\\ a_i & +\infty \end{bmatrix} =\begin{bmatrix} f(i) & f(i-1) \end{bmatrix} \]为了方便,我们定义 \(t=\text{LCA}(u,v)\),\(k=3\) 时亦然。
把中间的转移矩阵存起来倍增预处理一下,询问的时候,因为正着走和倒着走没有区别,我们把 \(u\to t\to v\) 拆成 \(u\to t,v\to t\) 两条链,以 \(u\to t\) 为例:
初始向量矩阵:
\[\begin{bmatrix} a_u & +\infty \end{bmatrix} \]然后把 \(fa_u\to t\) 上的转移矩阵全乘起来,就得到了 \(u\to t\) 这条链上的答案。
类似地处理 \(v\to t\),接下来考虑合并答案。
因为 \(k=2\),只有两种可能:\(u\) 走到 \(t\) 再走到 \(v\),或者不经过 \(t\),直接从 \(t\) 在 \(u\to v\) 路径上的两个子节点处穿过。
记 \(u\to t\) 的矩阵为 \(P\),\(v\to t\) 的矩阵为 \(Q\),因为可以写作一维向量的形式,为了方便,我们直接将 \(P\) 中的元素用类似序列下标的形式表示,即 \(P(0),P(1)\)。下面 \(k=3\) 的情况里我们仍采用这种称呼。
针对两种情况,答案分别为 \(P(0)+Q(0)-a_t,P(1)+Q(1)\),两者取 \(\operatorname {min}\) 即可。
时空复杂度 \(\mathcal O(2^3\times (n+m)\log n)\)。
k=3:
其实 \(k=3\) 大体思路和 \(k=2\) 完全一致,只不过有一个小细节:答案路径上的节点不一定都是 \(u\to v\) 这条链上的。
原因很简单,比如链上的点权都是 \(10^9\) 级别,而与链相连的节点中有一个点权是 1,那走这个点显然更优。
题解里大部分做法是将距离设入状态中,我当时并没有想到,而是直接把链接出去的点再设计一个方程。
还是先考虑一条链上的暴力,因为与 \(u\) 相连的点中,只有点权最小的有效,设这个最小点权为 \(c_u\)。
在 \(k=2\) 的情况上再加一条:设 \(g(i)\) 表示走到 \(i\) 连接的点上的最小路径花费。
状态转移方程:
\[f(i)=\min\{f(i-1)+a_i,f(i-2)+a_i,f(i-3)+a_i,g(i-1)+a_i,g(i-2)+a_i\}\\ g(i)=\min\{f(i-1)+c_i,f(i-2)+c_i,g(i-1)+c_i\} \]考虑将这个东西写成矩阵,那么样子就长这样:
\[\begin{bmatrix} f(i-1) & f(i-2) & f(i-3) & g(i-1) & g(i-2) \end{bmatrix} \times \begin{bmatrix} a_i & 0 & +\infty & b_i & +\infty\\ a_i & +\infty & 0 & b_i & +\infty\\ a_i & +\infty & +\infty & +\infty & +\infty\\ a_i & +\infty & +\infty & b_i & 0\\ a_i & +\infty & +\infty & +\infty & +\infty \end{bmatrix} \\=\begin{bmatrix} f(i) & f(i-1) & f(i - 2) & g(i) & g(i-1) \end{bmatrix} \]倍增预处理和查询就很类似了,略过。
最后的合并情况很多,这里我直接把所有情况对应的式子列出来,因为用文字真的很难写出来 QAQ,理解一下叭 awa,有兴趣可以自己推一下,如果实在嫌我的方法麻烦还是看别的大佬的题解吧 qwq:
-
\(P(0)+Q(0)-a_t\)
-
\(P(3)+ Q(3)-c_t\)
-
\(P(1)+Q(1)\)
-
\(P(1)+Q(2)\)
-
\(P(1)+Q(4)\)
-
\(P(4)+Q(1)\)
-
\(P(2)+Q(1)\)
所有情况取 \(\operatorname{min}\) 即可。时间复杂度 \(\mathcal O(5^3\times (n+m)\log n)\)。
Code
// Problem: P8820 [CSP-S 2022] 数据传输
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P8820
// Memory Limit: 1 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
using i64 = long long;
const i64 INF = 1e16;
const int maxn = 2e5 + 5;
std::vector<int> G[maxn];
int n,m;
int f[maxn][20],lg[maxn],dep[maxn];
i64 d[maxn],val[maxn],b[maxn];
void dfs(int u,int fa) {
d[u] = d[fa] + val[u];
for(auto& v : G[u]) {
if(v == fa)continue ;
dep[v] = dep[u] + 1;
f[v][0] = u;
for(int k = 1;(1 << k) <= dep[v];++ k)
f[v][k] = f[f[v][k - 1]][k - 1];
dfs(v , u);
}
return ;
}
int LCA(int u,int v) {
if(dep[u] < dep[v])std::swap(u , v);
for(int k = lg[dep[u]];~ k;-- k) {
if(dep[u] - (1 << k) >= dep[v]) {
u = f[u][k];
}
if(u == v)return u;
}
for(int k = lg[dep[u]];~ k;-- k) {
if(f[u][k] != f[v][k]) {
u = f[u][k];
v = f[v][k];
}
}
return f[u][0];
}
namespace subtask_1 {
int main() {
while(m --) {
int u,v;
scanf("%d %d",&u,&v);
int t = LCA(u , v);
printf("%lld\n",d[u] + d[v] - d[t] - d[f[t][0]]);
}
return 0;
}
}
namespace subtask_2 {
struct matrix {
i64 g[2][2];
matrix() {
g[0][0] = g[0][1] = g[1][0] = g[1][1] = INF;
}
void init() {
g[0][0] = g[0][1] = g[1][0] = g[1][1] = INF;
return ;
}
matrix operator * (const matrix& p)const {
matrix a;
for(int q = 0;q < 2;++ q) {
for(int i = 0;i < 2;++ i) {
for(int j = 0;j < 2;++ j) {
a.g[i][j] = std::min(a.g[i][j] , g[i][q] + p.g[q][j]);
}
}
}
return a;
}
}S[maxn][18];
void DFS(int u,int fa) {
for(auto& v : G[u]) {
if(v == fa)continue ;
S[v][0].g[0][0] = val[v];
S[v][0].g[0][1] = 0;
S[v][0].g[1][0] = val[v];
S[v][0].g[1][1] = INF;
for(int k = 1;(1 << k) <= dep[v];++ k)
S[v][k] = S[v][k - 1] * S[f[v][k - 1]][k - 1];
DFS(v , u);
}
return ;
}
int main() {
S[1][0].g[0][0] = val[1];
S[1][0].g[0][1] = 0;
S[1][0].g[1][0] = val[1];
S[1][0].g[1][1] = INF;
DFS(1 , 0);
while(m --) {
int u,v,t;
scanf("%d %d",&u,&v);
if(u == v) {
printf("%lld\n",val[u]);
continue ;
}
t = LCA(u , v);
i64 ans = INF;
matrix F,P;
F.g[0][0] = val[u];
P.g[0][0] = val[v];
int x = f[u][0];
if(u != t) {
for(int k = lg[dep[x]];~ k;-- k) {
if(dep[x] < dep[t])break ;
if(dep[f[x][k]] >= dep[t]) {
F = F * S[x][k];
x = f[x][k];
}
}
while(dep[x] >= dep[t])F = F * S[x][0],x = f[x][0];
}
if(v != t) {
x = f[v][0];
for(int k = lg[dep[x]];~ k;-- k) {
if(dep[x] < dep[t])break ;
if(dep[f[x][k]] >= dep[t]) {
P = P * S[x][k];
x = f[x][k];
}
}
while(dep[x] >= dep[t])P = P * S[x][0],x = f[x][0];
}
ans = std::min(F.g[0][0] + P.g[0][0] - val[t] , F.g[0][1] + P.g[0][1]);
printf("%lld\n",ans);
}
return 0;
}
}
namespace subtask_3 {
struct matrix {
i64 g[5][5];
matrix() {
for(int i = 0;i < 5;++ i)
for(int j = 0;j < 5;++ j)
g[i][j] = INF;
}
void init() {
for(int i = 0;i < 5;++ i)
for(int j = 0;j < 5;++ j)
g[i][j] = INF;
}
matrix operator * (const matrix& p)const {
matrix c;
for(int k = 0;k < 5;++ k)
for(int i = 0;i < 5;++ i)
for(int j = 0;j < 5;++ j)
c.g[i][j] = std::min(c.g[i][j] , g[i][k] + p.g[k][j]);
return c;
}
}S[maxn][18];
void getinit(int u) {
S[u][0].g[0][0] = val[u];
S[u][0].g[0][1] = 0;
S[u][0].g[0][3] = b[u];
S[u][0].g[1][0] = val[u];
S[u][0].g[1][2] = 0;
S[u][0].g[1][3] = b[u];
S[u][0].g[2][0] = val[u];
S[u][0].g[3][0] = val[u];
S[u][0].g[3][3] = b[u];
S[u][0].g[3][4] = 0;
S[u][0].g[4][0] = val[u];
return ;
}
void DFS(int u,int fa) {
for(auto& v : G[u]) {
if(v == fa)continue ;
getinit(v);
for(int k = 1;(1 << k) <= dep[v];++ k)
S[v][k] = S[v][k - 1] * S[f[v][k - 1]][k - 1];
DFS(v , u);
}
return ;
}
int main() {
for(int i = 1;i <= n;++ i) {
b[i] = INF;
for(auto& v : G[i]) {
b[i] = std::min(b[i] , val[v]);
}
}
getinit(1);
DFS(1 , 0);
while(m --) {
int u,v,t;
scanf("%d %d",&u,&v);
if(u == v) {
printf("%lld\n",val[u]);
continue ;
}
t = LCA(u , v);
i64 ans = INF;
matrix F,P;
F.g[0][0] = val[u];
P.g[0][0] = val[v];
int x = f[u][0];
if(u != t) {
for(int k = lg[dep[x]];~ k;-- k) {
if(dep[x] < dep[t])break ;
if(dep[f[x][k]] >= dep[t]) {
F = F * S[x][k];
x = f[x][k];
}
}
while(dep[x] >= dep[t])F = F * S[x][0],x = f[x][0];
}
if(v != t) {
x = f[v][0];
for(int k = lg[dep[x]];~ k;-- k) {
if(dep[x] < dep[t])break ;
if(dep[f[x][k]] >= dep[t]) {
P = P * S[x][k];
x = f[x][k];
}
}
while(dep[x] >= dep[t])P = P * S[x][0],x = f[x][0];
}
ans = std::min(ans , F.g[0][0] + P.g[0][0] - val[t]);
ans = std::min(ans , F.g[0][3] + P.g[0][3] - b[t]);
ans = std::min(ans , F.g[0][1] + P.g[0][1]);
ans = std::min(ans , F.g[0][1] + P.g[0][2]);
ans = std::min(ans , F.g[0][1] + P.g[0][4]);
ans = std::min(ans , F.g[0][4] + P.g[0][1]);
ans = std::min(ans , F.g[0][2] + P.g[0][1]);
printf("%lld\n",ans);
}
return 0;
}
}
int k;
int main() {
scanf("%d %d %d",&n,&m,&k);
for(int i = 1;i <= n;++ i)
scanf("%lld",&val[i]);
for(int i = 1;i < n;++ i) {
int u,v;
scanf("%d %d",&u,&v);
G[u].pb(v);
G[v].pb(u);
}
dep[0] = -1;
for(int i = 2;i <= n;++ i)
lg[i] = lg[i >> 1] + 1;
dfs(1 , 0);
if(k == 1) {
subtask_1::main();
return 0;
}
if(k == 2) {
subtask_2::main();
return 0;
}
else subtask_3::main();
return 0;
}
完结撒花✿✿ヽ(°▽°)ノ✿
标签:infty,bmatrix,min,int,题解,dep,2022,ans,CSP From: https://www.cnblogs.com/663B/p/16873225.html