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

dyc2022 · 2026-10-20 16:47:35 · 题解

更好的阅读体验

比较深刻，比较困难。

首先有一个初步的观察，就是每个点每次被从大根堆中取出来的时候，最短路都会减小。这就意味着答案有着 O(n^2) 的上界。

把仙人掌以 1 为根拎起来，则每个环都有一个“环顶”，即与 1 距离最近的节点。容易发现，我们每次更新这个环，都是以某个目前的最短距离 d 进入环顶，然后分别沿着顺时针、逆时针方向走一遍这个环（不妨假设在环上，环顶顺时针方向的点编号比逆时针方向的点小），如果我当前用于更新的路径长度已经 \ge 当前走到节点的最短路，就退出。

更进一步地，我们发现假设一个环的环顶是 u，在某个时刻我们已经确定了仙人掌上 u 子树的所有最短路数组 d，现在又一次经过了 u，并且让 d_u 减少了 i，则在完成该子树的所有更新后，对于这个子树内的所有点 v，都有 d'_v = d_v - i。这就意味着，这个子树多进行的更新操作的次数，仅与整个子树最短路减少的量，也就是上文的 i 有关。我们不妨考虑把这个 i 写入状态进行 dp。

在仙人掌上由于存在环，所以问题比较复杂，考虑建立圆方树。于是考虑 f_{u, i} 表示圆方树上 u 子树内，所有圆点的最短路确定后，要让所有圆点的最短路均减少 i，要多进行多少次更新。首先考虑圆点的转移：这个很简单，对于圆点 u，要先花费 1 的代价将 u 最短路减少 i，然后把它所在的所有环（在圆方树上就是它的所有儿子）的更新次数加起来即可。也就是对于圆点 u，有 \displaystyle{f_{u, i} = 1 + \sum_{v \isin son_u} f_{v, i}}。

再考虑方点的转移。一个方点 u 对应的是一个不包括环顶的环，我们关心的是一个点会被更新 1 次还是 2 次。首先显然，从环顶开始，顺时针走 1/2 环长走到的所有点一定都只会被更新一次，因为我们第一次走到的就是最短路。对于其他点，假设对于圆方树上 u 的儿子 v，记 x_v 表示从环顶顺时针走到 v 的距离，y_v 表示逆时针走到 v 的距离，那假设更新之前，环顶的最短路是 D，则更新之前 v 的最短路是 D + y_v，第一次更新时到 v 的路径长是 D - i + x_v。所以如果 x_v - i \ge y_v，也就是 x_v - y_v \ge i，就只会产生一次更新，否则产生两次更新。

形式化地，我们记 w_v 表示第一次走到这个点比第二次走到这个点远多少（如果第一次到达就是最短路，则 w_v = 0），其中对于环顶逆时针方向的邻居它只会被走一次，因此 w_v = 0；对于其他点，有 w_v = \max(0, x_v - y_v)。

• 如果 w_v = 0 或者 w_v \ge i，则当前点 v 只产生一次更新，会直接让 v 的最短路减少 i，即 f_{u ,i} \leftarrow f_{v, i}。
• 如果 0 < w_v < i，则 v 会产生两次更新，第一次更新会让 v 最短路减少 i-w_v，第二次会让最短路减少 w_v，即 f_{u, i} \leftarrow f_{v, w_v} + f_{v, i - w_v}。

显然对于 f_{u, i}，第二维有效状态数是 O(sz_u)，其中 sz_u 表示 u 的子树大小。至此做到 O(n^2)。

接下来考虑优化这个 dp。我们充分发扬人类智慧，记 g_{u, i} 表示 f_{u, *} 在第二维上的差分数组，我们来看看几类 f 转移在 g 上有何表现。

• 对于 u 为圆点或 w_v = 0 的情形，有转移 f_{u, i} \leftarrow f_{v, i}：容易发现和的差分等于差分的和，所以这个操作等价于 g_{u, *} 和 g_{v, *} 对位相加。

• 对于 u 为方点且 w_v > 0 的情形，有转移 f_{u, i} \leftarrow f_{v, \min(i, w_v)} + f_{v, \max(i - w_v, 0)}，容易发现这个式子和上面讨论的两种情况等价。则这个时候我们先考虑 h_i = f_{v, \min(i, w_v)} + f_{v, \max(i - w_v, 0)} 这个式子的差分数组，后面再加到 g_{u, *} 上即可。容易发现，

  • 当 i \le w_v，f_{v, \max(i-w_v, 0)} = 0，因此 h_i - h_{i-1} = f_{v, i} - f_{v, i-1} = g_{v, i}。
  • 当 i > w_v，f_{v, \min(i, w_v)} = f_{v, w_v}，是常数。因此 h_i - h_{i-1} = f_{v, i-w_v} - f_{v, i-w_v-1} = g_{v, i-w_v}。

  我们发现这种转移的实质是，把 g_v 的前 w_v 项复制一遍再拼接到 g_v 的前面，最后把拼接后的结果对位加到 g_{u, *} 上！

我们可以使用 map 维护每个 u 的 g_{u, *}，对位加可以通过 map 的启发式合并实现。现在问题在于“把 g_v 的前 w_v 项复制一遍拼在前面”这个操作要如何实现。实际上暴力即可，简要证明如下。

由于 g_{v, *} 的有效下标是子树大小量级的，且容易发现 w_v 是环长量级的，在圆方树上等价于 v 的兄弟个数。即要证，对于一棵树，记 a_i 为 i 子树大小，b_i 为 i 的兄弟个数，则所有节点 \min(a_i, b_i) 之和为 O(n \log n)。

考虑将 i 的兄弟个数放缩为 i 的所有兄弟的子树大小之和，则一个点的贡献，就是它的子树大小与其他兄弟的子树大小之和的 \min。

容易发现假如一个点 u 在其祖先 f 处产生了 1 的贡献，则 f 的父亲的子树大小相较于 f 的子树大小必然至少翻倍。因此一个点至多产生 O(\log n) 次贡献，总和必然是 O(n \log n) 量级的。

至此我们在每个节点处维护 map，若 w_v > 0，则直接暴力取出 \le w_v 的所有 i，将其复制一遍。同时我们需要对每个点的 map 维护一个全局平移标记，因为我们拼接之后所有原来存在的下标都会向右平移 w_v。同时我们再维护当前 map 中存的所有数字之和，这就是 f_{v, +\infty} 的取值。

最后答案就是 f_{1, +\infty}，取出 1 处的 map 的所有数字之和即可。

至此问题得到解决，由于有 O(n \log n) 次 map 操作，时间复杂度为 O(n \log^2 n)。由于有一只 \log 来源于启发式合并，常数很小，略微卡常即可通过全部 hack。代码中省略了快读部分。

#include<bits/stdc++.h>
#define endl '\n'
#define N 1000006
using namespace std;
struct IO {} io;
using i64=long long;
int n,m,cnt,w[N],son[N];
int tot,dfs_clock,tp,low[N],dfn[N],stk[N];
vector<int> G[N],tG[N];
pair<int,i64> change[N];
void tarjan(int u)
{
  dfn[u]=low[u]=++dfs_clock,stk[++tp]=u;
  for(int v:G[u])if(!dfn[v])
  {
    tarjan(v),low[u]=min(low[u],low[v]);
    if(low[v]>=dfn[u])
    {
      int x=++tot; vector<int> vec={u};
      do x=stk[tp--],vec.push_back(x); while(x!=v);
      for(int i:vec)
        tG[tot].push_back(i),tG[i].push_back(tot);
    }
  } else low[u]=min(low[u],dfn[v]);
}
struct DS {
  map<int,i64> mp;
  i64 tag,sum;
  inline size_t size() {return mp.size();}
  inline void clear() {mp.clear(),tag=sum=0;}
  inline void add(int k,i64 x) {mp[k-tag]+=x,sum+=x;}
  inline void update(int w) // 把 <= w 的在前面拼接一遍
  {
    tp=0;
    for(auto it=mp.begin();it!=mp.end();it++)
      if(tag+it->first<=w)change[++tp]={tag+it->first,it->second};
      else break;
    tag+=w;
    for(int i=1;i<=tp;i++)add(change[i].first,change[i].second);
  }
} t[N];
inline void merge(int u,int v) // v -> u
{
  if(t[u].size()<t[v].size())
    t[u].mp.swap(t[v].mp),swap(t[u].tag,t[v].tag),swap(t[u].sum,t[v].sum);
  for(auto x:t[v].mp)t[u].add(x.first+t[v].tag,x.second);
}
void dfs(int u,int fa)
{
  if(u<=n)
  {
    t[u].add(1,1);
    for(int v:tG[u])if(v!=fa)dfs(v,u),merge(u,v);
    return;
  }
  int pos=-1,sz=tG[u].size();
  for(int i=0;i<sz;i++)
    if(tG[u][i]==fa)pos=i; else dfs(tG[u][i],u);
  cnt=0;
  for(int i=pos+1;i<sz;i++)son[++cnt]=tG[u][i];
  for(int i=0;i<pos;i++)son[++cnt]=tG[u][i];
  if(son[1]>son[cnt])reverse(son+1,son+1+cnt);
  for(int i=1;i<=cnt;i++)w[son[i]]=max(0,i*2-cnt-1);
  w[son[cnt]]=0;
  for(int i=1;i<=cnt;i++)
  {
    int v=son[i];
    if(!w[v])merge(u,v); else t[v].update(w[v]),merge(u,v);
  }
}
void solve()
{
  tot=n=io.read(),m=io.read();
  for(int i=1;i<=2*n;i++)
    tG[i].clear(),G[i].clear(),dfn[i]=low[i]=0,t[i].clear();
  for(int i=1,u,v;i<=m;i++)
    u=io.read(),v=io.read(),G[u].push_back(v),G[v].push_back(u);
  dfs_clock=tp=0,tarjan(1),dfs(1,0);
  io.writeln(t[1].sum);
}
main()
{
  io.read(); int T=io.read();
  while(T--)solve();
  return 0;
}