题解：P17724 [SCP-S 2026] 路短最 / path

· · 题解

题解：P17724 [SCP-S 2026] 路短最 / path

哎，我不会紫，我是 fvv。

（写题写了一半，看了一下题面）

欸，怎么变黑题了🫨。

思路

看到题目，意识到我们有两条手，于是考虑模拟题意。

使用一个优先队列维护二元组 (u,d)，每次优先取出距离最大的二元组；距离相同时，优先取出节点编号较小的二元组。如果取出的距离与当前记录的距离不同，就说明这个二元组已经过期，直接丢弃；否则将答案加一，并尝试松弛相邻节点。

这种方法能够直接求出答案，but 一个节点的距离可能被多次更新，每次更新又会向优先队列插入新的二元组，非常浪费😒。

既然题目只要求最终的计数器 C，我们不妨不再模拟每次出队，而是直接统计每个节点对答案的贡献。

先考虑原图是一棵树的情况🤔。

从节点 1 出发，每个节点都只有一条简单路径可以到达。沿着这条路径传播时，不会出现另外一条路径使节点的距离变小。因此，每个节点最终都只会产生一次有效出队。于是有 C = n。

这意味着，如果原图没有环，问题就非常简单😆。

那么，额外的贡献来自哪里？

考虑一个简单环。当从环的一端开始扩展时，距离较大的候选状态会优先出队。如果两个方向上的候选状态距离相同，则编号较小的节点先出队，而它继续产生的新候选状态可能具有更大的距离。

这样，算法就可能先沿着环的一侧走得较远，再由另一侧传来的更短路径更新某些节点。这些节点可能再次产生有效出队，使得答案超过 n😲。

因此，我们需要解决如何快速统计每个环造成的额外贡献，以及这些贡献如何通过环上的其他节点传递到整张图？

意识到我们有眼睛，于是考虑观察题面👀。

我们发现题目中提到了仙人掌图，于是我们可以利用仙人掌图的性质（每条边至多属于一个简单环），把环变成树。

我们以节点 1 为根进行搜索，记录每个节点的父节点、深度等信息。

对于一条连接节点 u 和其祖先 v 的返祖边，设 DFS 树上从 v 到 u 的路径为

v,p_1,p_2,\ldots,p_{k-1}=u

加上边 (u,v) 后，这条路径恰好构成一个包含 k 个节点的简单环。

如果直接保留原来的树形结构，环上的两个方向会让 DP 的转移变得复杂🤯。因此，我们将路径上的节点 p_1,\ldots,p_{k-1} 全部改为 v 的儿子。这样，原图中的环就被转化成了一棵树中的多个分支。

对于不在环上的普通树边，则保持原来的父子关系不变。 不过，直接将环改成一棵树会丢失两侧路径之间的距离差。因此，我们还需要给每个节点记录一个量 h，用它来描述环造成的影响。

考虑上面的环。节点 v 在环上的两个邻居分别是 p_1 和 u。

两个方向的候选状态具有相同的初始距离，因此编号较小的一端会优先展开。假设 p_1<u，A...d 算法便会优先沿着 v\rightarrow p_1\rightarrow p_2\rightarrow\cdots 这一方向扩展。 对于节点 p_i，沿这条路径到达它需要经过 i 条边，而从另一侧到达它需要经过 k-i 条边。两条路径的长度之差是 i-(k-i)=2i-k。

当 2i>k 时，沿优先扩展方向到达该节点的路径更长。此时另一侧可能通过更短的路径更新它，因此它的 h 应当为 h_{p_i}=2i-k。

So，当 p_1<u 时：

如果 u<p_1，则优先扩展的方向相反。此时令 j=k-i，同理可得：

这样，每个环上的节点就获得了相应的 h。完成所有环的处理后，原图转化为一棵带偏移量的辅助树😁。

接下来就是 DP 了。

If 一个子树完全不涉及环，那么它的每个节点只贡献一次，直接累计即可。

对于存在环的分支，则需要根据 h，统计某一份贡献会被保留一次还是产生额外贡献。

为此，我们给每个节点 u 维护一个 DP 数组 F_u。 其中，F_{u_i} 表示将 u 的子树中的贡献汇总到 u 后，落在偏移位置 i 上的贡献数量。

初始时，每个节点本身至少产生一次有效出队，因此初始化时需要令 F_{u_1}\gets F_{u_1}+1。

合并时设 v 是 u 的儿子，其偏移量为 h_v。

考虑 v 的 DP 中的一项 F_{v_i}。将这份贡献向父节点合并时，首先需要考虑偏移量造成的位置变化，因此将它转移到位置 i+h_v：

F_{u_{i+h_v}} = F_{u_{i+h_v}} + F_{v_i}

当然，只有 i+h_v\le s_u 时，这个位置才有效。其中 s_u 表示 u 的子树大小。

此外，当 i\le h_v 时，环上较长路径与较短路径之间的距离差还会使这份贡献在原偏移位置保留一份。因此，当 i \le h_v 时还需要进行额外转移：F_{u_i}=F_{u_i}+F_{v_i}。

合并完所有儿子后，再加上节点 u 自身的初始贡献，就得到了完整的 F_u，非常的优雅🤫。

但是我们可以发现，我们并不能对每个节点都独立维护一个 DP 数组，因为合并一个儿子时，可能需要遍历整个儿子的子树大小。

因此我们需要优化。

观察 DP 转移可以发现，合并一个儿子时，最主要的操作是将它的整个 DP 数组向后平移 h_v 个位置。

如果能够让儿子的数组与父亲的数组共享一部分空间，那么这次平移就不必真的逐项执行。

于是，我们选择每个节点子树最大的儿子作为重儿子，记为 w_u。

对于重儿子 v=w_u，将它的 DP 数组起始位置设置为 l_v=l_u+h_v。

这样，儿子的第 i 项与父亲的第 i+h_v 项恰好位于同一个全局数组位置：

F_{v_i}\longleftrightarrow F_{u_{i+h_v}}

因此，向后平移的转移已经通过数组布局自然完成，不需要逐项复制。

对于需要保留在原位置的前缀部分，只需将重儿子的前 \min(h_v,s_v) 项复制到父亲的对应前缀位置即可。

至于轻儿子嘛……由于它的数组不与父亲共享空间，仍然需要逐项合并😱。

完成整棵辅助树的 DP 后，根节点 1 的 DP 数组已经有了所有节点的贡献。

因此，只需要将根节点的所有有效位置求和：

C=\sum_{i=1}^{n}F_{1_i}

注意这里只统计根节点的 DP 数组。因为重链优化会让多个节点的 DP 数组共享全局数组中的部分位置，不能把每个节点的数组重复累加。

::::info[如果你需要正确性证明🧐] 首先，对于每条返祖边，仙人掌图的性质 can 保证它与 DFS 树上的对应路径构成唯一的简单环。按编号较小的一侧确定优先扩展方向后，利用两侧路径长度之差即可得到相应的偏移量 h。

然后假设每个儿子的 DP 都正确。将儿子的贡献向父节点转移时，偏移后的位置记录了正常的贡献传递，而满足条件的原位置则记录了环产生的额外贡献。再加入节点自身的一次基本贡献，便能得到正确的父节点 DP。因此，由叶节点向根节点归纳，整棵树的 DP 都正确🤓☝️。

Finally，根节点包含所有原图节点的贡献。将其全部有效位置相加，得到的就是所有有效出队次数之和，也就是题目要求的 C。

我能证明！

注意到跑得还不慢，截止交审时是最优解第二页。

代码

::::success[代码]

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;

const int MAXN = 500005;
const int MAXE = 1500005;
const int MAXF = 12000005;

int T, c, n, m, ans;
int head[MAXN], to[2 * MAXE], nxt[2 * MAXE], ecnt;
int dfn[MAXN], dep[MAXN], fa[MAXN], fedge[MAXN], fnew[MAXN], h[MAXN];
int path[MAXN], f[MAXF], tim, top;
int head2[MAXN], to2[MAXN], nxt2[MAXN], ecnt2;
int order[MAXN], s[MAXN], w[MAXN], l[MAXN];
int stk[MAXN], cedge[MAXN];

void mian()
{
    cin >> n >> m;
    ecnt = ans = 0;
    for (int i = 1; i <= n; i++)
        head[i] = dfn[i] = dep[i] = fa[i] = fedge[i] = fnew[i] = h[i] = 0;
    for (int u, v, i = 1; i <= m; i++)
    {
        cin >> u >> v;
        ecnt++;
        to[ecnt] = v;
        nxt[ecnt] = head[u];
        head[u] = ecnt;
        ecnt++;
        to[ecnt] = u;
        nxt[ecnt] = head[v];
        head[v] = ecnt;
    }
    tim = top = 0;
    stk[++top] = 1;
    dfn[1] = ++tim;
    cedge[top] = head[1];
    while (top)
    {
        int u = stk[top];
        int e = cedge[top];
        if (e == 0)
        {
            top--;
            continue;
        }
        cedge[top] = nxt[e];
        int v = to[e];
        if (v == fa[u])
            continue;
        if (!dfn[v])
        {
            dfn[v] = ++tim;
            dep[v] = dep[u] + 1;
            fa[v] = u;
            fedge[v] = e;
            fnew[v] = u;
            h[v] = 0;
            stk[++top] = v;
            cedge[top] = head[v];
        }
        else if (dep[v] < dep[u])
        {
            int del = dep[u] - dep[v] + 1;
            int x = u;
            for (int i = del - 1; i >= 0; i--)
            {
                path[i] = x;
                if (i > 0)
                    x = fa[x];
            }
            int a = path[1];
            int b = u;
            if (a < b)
            {
                for (int i = 1; i <= del - 1; i++)
                {
                    int node = path[i];
                    int nh = 0;
                    if (i < del - 1 && 2 * i > del)
                        nh = 2 * i - del;
                    fnew[node] = v;
                    h[node] = nh;
                }
            }
            else
            {
                for (int i = 1; i <= del - 1; i++)
                {
                    int node = path[i];
                    int j = del - i;
                    int nh = 0;
                    if (j < del - 1 && 2 * j > del)
                        nh = 2 * j - del;
                    fnew[node] = v;
                    h[node] = nh;
                }
            }
        }
    }
    ecnt2 = 0;
    for (int i = 1; i <= n; i++)
        head2[i] = 0;
    for (int i = 2; i <= n; i++)
    {
        int p = fnew[i];
        ecnt2++;
        to2[ecnt2] = i;
        nxt2[ecnt2] = head2[p];
        head2[p] = ecnt2;
    }
    top = 0;
    stk[++top] = 1;
    int tot = 0;
    while (top)
    {
        int u = stk[top--];
        order[++tot] = u;
        for (int e = head2[u]; e; e = nxt2[e])
        {
            int v = to2[e];
            stk[++top] = v;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        s[i] = 1;
        w[i] = 0;
    }
    for (int i = tot; i >= 1; i--)
    {
        int u = order[i];
        s[u] = 1;
        w[u] = 0;
        for (int e = head2[u]; e; e = nxt2[e])
        {
            int v = to2[e];
            s[u] += s[v];
            if (w[u] == 0 || s[v] > s[w[u]])
                w[u] = v;
        }
    }
    int ptr = 1;
    l[1] = ptr;
    ptr += s[1];
    for (int i = 1; i <= tot; i++)
    {
        int u = order[i];
        for (int e = head2[u]; e; e = nxt2[e])
        {
            int v = to2[e];
            if (v == w[u])
                l[v] = l[u] + h[v];
            else
            {
                l[v] = ptr;
                ptr += s[v];
            }
        }
    }
    for (int i = 1; i < ptr; i++)
        f[i] = 0;
    for (int idx = tot; idx >= 1; idx--)
    {
        int u = order[idx];
        if (w[u] != 0)
        {
            for (int i = 1; i <= min(h[w[u]], s[w[u]]); i++)
                f[l[u] + i - 1] = f[l[w[u]] + i - 1];
        }
        for (int e = head2[u]; e; e = nxt2[e])
        {
            int v = to2[e];
            if (v == w[u])
                continue;
            int *fv = f + l[v] - 1;
            int *fu = f + l[u] - 1;
            for (int i = 1; i <= s[v]; i++)
            {
                int val = fv[i];
                if (val == 0)
                    continue;
                if (i <= h[v])
                    fu[i] += val;
                if (h[v] + i <= s[u])
                    fu[h[v] + i] += val;
            }
        }
        f[l[u]] += 1;
    }
    for (int i = 1; i <= n; i++)
        ans += f[l[1] + i - 1];
    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> c >> T;
    while (T--)
        mian();
    return 0;
}

::::