CF671D Roads in Yusland 做题记录

题意简述

给定一棵 $n$ 个点的以 $1$ 为根的树。

有 $m$ 条路径 $(x,y)$，保证 $y$ 是 $x$ 或 $x$ 的祖先，每条路径有一个权值。

你要在这些路径中选择若干条路径，使它们能覆盖每条边，同时权值和最小。

$n,m\le3\times10^5$。时限 $\rm{4s}$，内存限制 $\boldsymbol{\rm{256MB}}$。

Part 1 朴素 DP

记 $g_u$ 表示将 $u$ 为根的子树完全覆盖需要的最小代价。但我们发现由于在覆盖时有可能将 $u$ 到 $1$ 的路径上一部分点也覆盖了，这样具有后效性。

考虑加一维。$g_{u,i}$ 表示覆盖以 $u$ 为根的子树，并且将 $u$ 深度为 $i$ 的祖先到 $u$ 的路径完全覆盖的最小代价。

记 $f_u=\min_{i=1}^{dep_u-1}g_{u,i},v\in son(u)$，则有 $g_{u,i}=\sum f_v+\min\{g_{v,i}-f_v\}$。

再考虑较深点为 $u$，较浅点深度为 $i$ 的路径。设其权值为 $w$。$g_{u,i}=\min\{g_{u,i},\sum f_v+w\}$。

答案为 $1$ 所有儿子 $f$ 的和。时间复杂度 $O(n^2)$。

Part 2 优化 1：整体 DP

不难想到，可以使用线段树合并维护这个 DP 过程。

线段树以 $g$ 第二维为下标。需支持全局加上 $\sum f_v$ 和 $-f_v$，单点修改（以当前节点为起点路径的贡献），区间查 $\min$，以及合并。节点 $u$ 的 $f$ 即为当前节点对应线段树的 $1\sim dep_u-1$ 中的最小值。

时间复杂度 $O(n\log n)$，空间复杂度 $\boldsymbol{O(n\log n)}$。对于 $\rm{256MB}$ 的内存来说有困难。

Code

int n,dep[N];ll f[N];
struct node{int v;ll w;};vector<node>p[N];
inline void dfs(int u,int fa)
{
    dep[u]=dep[fa]+1;ll sum=0;
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].to;if(v==fa)continue;
        dfs(v,u);sum+=f[v];sgt::update(root[v],-f[v]);sgt::merge(root[u],root[v],1,n);
    }
    for(node t:p[u])sgt::update(root[u],1,n,dep[t.v],t.w);
    sgt::update(root[u],sum);f[u]=sgt::query(root[u],1,n,1,dep[u]-1);
    if(f[u]>=1e17)IO::qwrite(-1),exit(0);
}

实测：精细使用内存可过，时间 $\rm{16.21s}$，内存 $\rm{195.82MB}$。

Part 3 优化 2：可并堆

我们发现由于动态开点权值线段树每插入 $1$ 个节点需要 $O(\log n)$ 的空间，并且在线段树中维护了大量无用状态信息，所以考虑使用空间消耗较小的数据结构来代替，并删除无用状态。

当 $dep_u\le j$ 时 $g_{u,j}$ 为无用状态且有大量的状态值为 $+\infty$。当我们删除所有无用状态时我们发现只需维护全局最小值，考虑使用堆。

具体的，在堆中存二元组 $(j,x)$，表示当前节点的 $g$ 中，下标为 $j$ 的位置有值，值为 $x$。全局加法打 $\rm{tag}$，单点修改往堆中新加元素，较小的那个必会先成为堆顶。在取堆顶时要先将无用状态弹掉。

时间复杂度 $O(n\log n)$，常数较小，空间复杂度 $\boldsymbol{O(n)}$。

小 trick：启发式合并优先队列

不会/不想写左偏树或其他可并堆怎么办？

众所周知，STL 的优先队列不支持合并。但通过启发式合并的方式能保证暴力合并时间复杂度正确。每次合并两个优先队列时总是将较小的那个中的元素暴力弹出插入较大的那个优先队列中。

对于每个元素来说，当且仅当它所在的优先队列比另一个小时，才会被弹出并插入到另一个优先队列中时，这样合并前后该元素所在优先队列的大小至少为原来的两倍，所以每个元素最多被删除/插入 $O(\log n)$ 次，删除/插入时间复杂度单次 $O(\log n)$，总时间复杂度 $O(n\log^2n)$。

STL 中大部分不支持合并的容器均可这样合并。

Code

ll f[N];int dep[N];
struct node{int dep;ll w;};bool operator<(const node&x,const node&y){return x.w>y.w;}
priority_queue<node>q[N];ll tag[N];
inline void merge(int x,int y)
{
    if(q[x].size()<q[y].size())swap(q[x],q[y]),swap(tag[x],tag[y]);
    while(!q[y].empty()){node t=q[y].top();q[y].pop();q[x].push((node){t.dep,t.w+tag[y]-tag[x]});}
}
inline void dfs(int u,int fa)
{
    dep[u]=dep[fa]+1;ll sum=0;
    for(dat i:p[u]){q[u].push((node){dep[i.x],i.w});}
    for(int i=head[u];i;i=e[i].nxt){int v=e[i].to;if(v==fa)continue;dfs(v,u);sum+=f[v];tag[v]-=f[v];merge(u,v);}
    tag[u]+=sum;while(!q[u].empty()&&q[u].top().dep>=dep[u])q[u].pop();
    if(q[u].empty())IO::qwrite(-1),exit(0);
    f[u]=q[u].top().w+tag[u];
}

实测：时间 $\rm{14.41s}$，内存 $\rm{87.80MB}$。虽然时间复杂度比线段树和左偏树要多一只 $\log$，但二叉堆常数十分优秀，所以其实际表现比线段树合并好，与实现一般的左偏树差不多，但注意 STL 容器内存消耗较大。此份代码在我提交时是最优解第二名。

Part 4 换种角度看问题：线性规划的对偶问题

在原问题的解不容易考虑时，可以考虑求解其对偶问题。

$\displaylines{\min z=cx\\ s.t.A x\geq b\\ \quad x\geq0}$ 的对偶问题为 $\displaylines{\max w=b^Ty\\ s.t.A^Ty\le c^T\\ y\geq0}$。

性质：对偶问题的最优解与原问题相等。

在此题中约束矩阵 $A_{i,j}$ 表示第 $i$ 条路径是否覆盖第 $j$ 个边，$b$ 为全 $1$ 矩阵，$x_i$ 为是否选第 $i$ 条路径，$c_i$ 是路径 $i$ 的权值。

其对偶问题中 $A^T_{i,j}$ 表示第 $i$ 个边是否被路径 $j$ 包含。问题转化为给每个边一个非负边权 $y_i$，使得每条路径上边权和不超过其权值，求最大边权和。

对偶问题相对较易解决。考虑贪心。按照深度枚举每条边，在当前填入满足所有限制的最大值。会影响到的祖先边与这条边必在同一路径上，将边权加到此处一定不劣。使用可并堆动态维护限制。代码与 DP 的类似。

时间复杂度 $O(n\log n)\sim O(n\log^2n)$，空间复杂度 $O(n)$。