题解：P10932 Freda的传呼机

Graph · 2024-11-20 17:07:22 · 题解

Update

• 边权的设定中，第二条将打错的 s 改为 p，并优化码风和 \LaTeX。

写圆方树板子，纠结了好久，用了一下午才把它弄懂，写篇题解回顾一下。

原题，双倍经验。

题意

给一棵仙人掌，每次询问两点之间的最短距离。

题解

我们讲讲如何发明圆方树的人怎么想到的。

首先，如果不考虑环的边权，那么缩点双连通分量，LCA 即可。

那么现在有环的边权，我们不可能像基环树那样对每个点进行操作，因为一条路径上如果全是环，那么复杂度就爆炸了。

于是，我们考虑越过一个环如何处理。

越过一个环，有两种情况，我们分别考虑。

first

注：我们假设 dep_x<dep_1<dep_y，dep_a 代表 a 在搜索树的深度。

这种情况我们只需要知道环上的点到环上深度最小的点的距离，我们设深度最小的点是 p。

那么我们可以建一个虚点（也就是方点，设其为 s），边权有如下设定：

• 同时去除环上的边。

这样我们就可以实现任意 i \ne p，i \to p 的路径最小值等于 i 和 p 树上两点之间的距离了。

second

注：我们设 dep_1 < dep_x，dep_1 <dep_y。

这种情况对于刚才的建树就失效了，因为刚才只统计了每个节点到深度最小的节点的距离。

但是，我们会发现一个很好的性质：这种情况只会在他们的最近公共祖先处出现一次。

于是我们就可以找到它们最短路径上最近公共祖先“下面”的两个点，我们设它们为 x_0,y_0，x \leftrightarrow x_0 和 y \leftrightarrow y_0 的距离可以 O(1) 求，接下来转化为求 x_0 \leftrightarrow y_0 的距离。

很简单，预处理每个环的前缀和，找到他们取个最小值即可。

总结

Tarjan 算法缩点是 O(n) 的，建圆方树是 O(n) 的。

LCA 我写的树剖，预处理 O(n)，查询 O(\log n)。

综上，时间复杂度为 O(n+m+q\log n)。

如果使用离线 Tarjan 求 LCA，可以做到优秀的线性复杂度。

关于代码实现

我们可以在 Tarjan 是顺便把圆方树建出来，但是有些复杂，我们结合重要代码（对于一个环建圆方树）看一看。（可以先看后面的代码部分，这里只是突出重点部分）

void help(int x,int y,int val) //val 是非树边边权 
{
    int cur=y,lst=val;
    while(cur!=x)
    {
        sum[cur]+=lst;
        sum[fa[cur]]+=sum[cur];
        lst=vval[cur];
        cur=fa[cur];
    }
    int sq=++ext;
    sum[sq]=sum[x]+lst; // 将所有边权放在方点上 
    sum[x]=0; // 方便后面处理 
    cur=y;
    while(cur!=fa[x])
    {
        int val=min(sum[cur],sum[sq]-sum[cur]); //再来一遍记录边权 
        Tree::add(cur,sq,val);
        cur=fa[cur];
    }
    return ;
}

我们注意到有一行 _tree.sum[x]=0，我们解读一下。