P8820 [CSP-S 2022 T4] 数据传输 题解

· · 题解

P8820 [CSP-S 2022 T4] 数据传输 O(k^3(n+m)) 做法

显然 k=1 时答案是 a-b 上所有点权之和。

可以得出 k=2 时是不用跳出 a-b 的链外的，因为 k=2 时跳出链，又跳回来是和直接跳一次是相同的。

设 dp_i 是走到 i 的最小答案，dp_{i-k} 走到距离 i 为 k 的最小答案。

于是 dp_i=\min(dp_{i-1},dp_{i-2})+v_p。

可以得出转移广义矩阵 [dp_{i-1},dp_{i-2}] \times \begin{bmatrix}v_i&0\\v_i&+\infty\end{bmatrix}=[dp_i,dp_{i-1}]。

设初始值为 [dp_a,+\infty] 然后从 a 的父亲一直乘转移矩阵到 b（dfn_a>dfn_b）。

可以发现 k=3 时可以跳到链外离链距离为 1 的点上，且如果跳到链外，它一定跳了 3 条边。

为了使每个点的转移矩阵只含有与它自己相关的值（因为这样好转移）

跳到链外离链距离为 1 的点上，即离当前点 i 距离为一的点。

可以发现无论从 i-2 跳到哪个离 i 距离为一的点上，就是跳到了 a-b 的链上也不会影响结果。

设 j 是 i 在 a-b 上前一个点，w_i 是离 i 距离为一的点的最小点权。

于是可以得到 [dp_j,dp_{j-1},dp_{j-2}] \times \begin{bmatrix}v_i&0&+\infty\\v_i&w_i&0\\v_i&+\infty&+\infty\end{bmatrix}=[dp_i,dp_{i-1},dp_{i-2}]。

初始值为 [dp_a,+\infty,+\infty]。

可以发现本题要维护的是链上的值的积，且没有修改，于是可以离线下来用带权并查集维护这个点到它祖先的积。

因为这个矩阵运算没有交换律，所以可以维护两个权，表示这个点到它祖先的积，它祖先到这个点的积。

然后在 c=lca(a,b) 处合并 fa_a-c ,c-b 的积即可，可以离线 O(n\alpha(n)) 求 lca，刚好可以用刚才的并查集维护。

实际上可以做到维护只带一个权的并查集，但是根节点带权的带权并查集不好维护，所以这里放了个容易写的双倍常数 O(k^3(n+m))。

最优解可以做到 O(k^3n+km)，用了只带一个权的并查集和单调性，但是显然维护单调性常数大于 k，所以最优解是 O(k^3n+k^2m)。

不知道比树剖好写多少倍。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int pt[200010],q[200010][2],n,m,ui;
long long v[200010],w[200010];
basic_string<int>e[200010],c[200010],s[200010];
void add(int a,int b){w[a]=min(w[a],v[b]),e[a]+=b;}
struct cube{
    long long g[3][3];
    void clear(){memset(g,0x3f3f,sizeof g);}
    void operator =(const int x){
        clear();
        for(int i=0;i<ui;i++)g[i][0]=v[x];
        for(int i=0;i+1<ui;i++)g[i][i+1]=0;
        if(ui==3)g[1][1]=w[x];
    }
    cube operator *(const cube &x){
        cube y;y.clear();
        for(int i=0;i<ui;i++)for(int j=0;j<ui;j++)for(int k=0;k<ui;k++)
            y.g[i][j]=min(y.g[i][j],g[i][k]+x.g[k][j]);
        return y;
    }
}pv[200010][2],res[200010],zero;
int find(int x){
    if(pt[x]==pt[pt[x]])return pt[x];
    int z=pt[x];pt[x]=find(pt[x]);
    pv[x][0]=pv[x][0]*pv[z][0];
    pv[x][1]=pv[z][1]*pv[x][1];
    return pt[x];
}
cube qry1(int x){if(x==pt[x])return zero;find(x);return pv[x][0];}
cube qry2(int x){if(x==pt[x])return zero;find(x);return pv[x][1];}
void dfs(int p,int f){
    for(int i:s[p]){
        if(pt[q[i][1]])swap(q[i][0],q[i][1]);
        if(pt[q[i][0]])res[i].clear(),res[i].g[0][0]=v[p],c[find(q[i][0])]+=i,q[i][1]=f;
    }
    pt[p]=p,pv[p][0]=p,pv[p][1]=p;for(int i:e[p])if(i!=f)dfs(i,p),pt[i]=p;
    for(int i:c[p])res[i]=res[i]*qry1(q[i][1])*pv[p][0]*qry2(q[i][0]);
}//这里的 find(q[i][0/1]) 一定是 p
int main(){
    scanf("%d%d%d",&n,&m,&ui);
    for(int i=0;i<ui;i++)for(int j=0;j<ui;j++)if(i!=j)zero.g[i][j]=1e18;//单位矩阵
    for(int i=1;i<=n;i++)scanf("%lld",&v[i]),w[i]=1e18;
    for(int i=1,a,b;i<n;i++)scanf("%d%d",&a,&b),add(a,b),add(b,a);
    for(int i=1;i<=m;i++)scanf("%d%d",&q[i][0],&q[i][1]),s[q[i][0]]+=i,s[q[i][1]]+=i;
    dfs(1,0);for(int i=1;i<=m;i++)printf("%lld\n",res[i].g[0][0]);
    return 0;
}

O(k^3n+km) 长这样

for(int i=heac[p];i;i=c[i].next){
    const int x=q[c[i].to][1],y=q[c[i].to][0];
    memset(ans,0x3f3f,48),ans[0][0]=v[x],ans[1][0]=v[y];
    if(x!=p){
        find(to[x],f),memset(ret,0x3f3f,24);
        for(int j=0;j<ui;++j)ret[j]=min(ret[j],ans[0][0]+pv[to[x]][0][j]);
        memcpy(ans[0],ret,24);//这里的 pv[x] 相当于上面的 pv[x][0]
    }
    if(y!=p){
        find(to[y],f),memset(ret,0x3f3f,24);
        for(int j=0;j<ui;++j)ret[j]=min(ret[j],ans[1][0]+pv[to[y]][0][j]);
        memcpy(ans[1],ret,24);
    }
    res[c[i].to]=ans[0][0]+ans[1][0]-v[p],now=ui-1;
    for(int j=ui-1;~j;--j)if(ans[1][j]<=ans[1][now])now=j;
    for(int j=0;j<ui;++j){if(now+j>ui)now--;res[c[i].to]=min(res[c[i].to],ans[0][j]+ans[1][now]);}
}

实际上所有求链上可合并信息并且没有修改或修改是从下往上的都可以这样做，甚至是某些线段树合并优化 dp。

赛时我傻了，用 2h 写了个巨长的树剖，离 100 就差 40 个字符，然后爆零。