[NOI2018]归程

并查集 倍增 最短路

---

题面

题面太长，难以概述，戳我

• $ex10pts\ tree$
• $50pts\ n\leq1500,Q\leq2000$
• $65pts\ off-line$
• $100pts\ n\leq2*10^5,m\leq4*10^5,Q\leq4*10^5$

解析

如果考场上不是盲目地码码码，而是开始先认真思考，我可以多得好多分呢

$50pts$算法

堆优化$SPFA$预处理$1$结点到各结点最短路。
然后从出发点出发，只走当时边权为$0$的边（海拔高于水位线），取能走到点中离$1$点最短距离即为答案。
本质上就是枚举由坐车转步行那个关键点，坐车无距离，步行距离取最短路，因而可以统计答案。
复杂度$O(Qn)$。
注意，只要时间允许，一定要在开头（每组数据开始）清空所有相关数组！！！

il void dfs(re int u,re int g)
{
    ans[0]=min(ans[0],dis[u]);
    for(re int i=h[u];i+1;i=e[i].nxt)
    {
        re int v=e[i].to;
        if(vis[v]||e[i].g<=g) continue;vis[v]=1;
        dfs(v,g);
    }
}
il void solve2()
{
    fp(i,1,qq)
    {
        re int v=gi(),p=gi();
        v=(v+k*las-1)%n+1;p=(p+k*las)%(s+1);
        ans[0]=2e9;
            fp(j,1,n) vis[j]=0;vis[v]=1;
        dfs(v,p);
        printf("%d\n",ans[0]);las=ans[0];vis[v]=0;
    }
}

$65pts$算法

离线意味着可以改变询问顺序。
怎么改变呢？
我们思维上可能更习惯于水位线上升。
水位线上升时，有边权的边数逐渐增多，我们应该加边。然而加边后怎么办？从出发点出发怎么走？总不能忽略那些边权为$0$的边吧。这是一条死路。
于是倒过来看。
水位线下降时，边权一一变为$0$，意味着两个端点可以合并视为一个点，两个端点到$1$号点的距离也可以取$min$（表现为取距$1$近的点为父亲）。该操作用并查集维护。

这样，把询问按水位线从高到低排序，把边按海拔从高到低排序，如果水位线降到海拔以下就把边的两端点并入并查集，即可做到$O(?Q)$复杂度。

il int find(re int x){return f[x]==x?x:f[x]=find(f[x]);}
il void Merge(re int x,re int y)
{
    re int fx=find(x),fy=find(y);
    if(fx==fy) return;
    if(dis[fx]>dis[fy]) f[fx]=fy;else f[fy]=fx;
}
il void solve1()
{
    fp(i,1,n) f[i]=i;
    fp(i,1,qq)
    {
        re int v=gi(),p=gi();
        v=(v-1)%n+1;p=p%(s+1);
        q[i]=(que){v,p,i};
    }
    sort(q+1,q+1+qq);
    sort(a+1,a+1+m);
    re int now=2e9,ysn=1;
    fp(i,1,qq)
    {
        if(now>q[i].g)
        {
            now=q[i].g;
            while(a[ysn].g>now)
            {
                Merge(a[ysn].u,a[ysn].v);ysn++;
            }
        }
        ans[q[i].id]=dis[find(q[i].v)];
    }
    fp(i,1,qq) printf("%d\n",ans[i]);
}

$ex10pts$算法

树的意义是树上任意两点路径唯一。
取$1$为根节点，我们只要从出发点一直向上走父亲就可以了，遇到一个有边权的就停下来答该点$dis$。
但是暴跳复杂度上限$O(Qn)$很虚。
于是倍增优化一下，维护父亲和区间内最小值（新技能$get$）即可。
话说回来，维护区间内最小值就是这样。

$$f[i][j]=min(f[i-1][j],f[i-1][fa[i-1][j]])$$
在区间$[j,j+2^{i-1}-1]$和区间$[j+2^{i-1},j+2^i-1]$中取$min$，即可得到区间$[j,j+2^i-1]$的最小值。
我们只倍增跳区间最小值为$0$的区间即可。
复杂度$O(Qlogn)$。

il void dfss(re int u,re int fa)
{
  for(re int i=h[u];i+1;i=e[i].nxt)
    {
      re int v=e[i].to;
      if(v==fa) continue;
      dfss(v,u);
      ff[0][v]=u;
      ff1[0][v]=e[i].g;
    }
}
il void solve3()
{
  dfss(1,0);
  fp(i,1,18) fp(j,1,n) ff[i][j]=ff[i-1][ff[i-1][j]],ff1[i][j]=min(ff1[i-1][j],ff1[i-1][ff[i-1][j]]);
  fp(i,1,qq)
  {
    re int v=gi(),p=gi();
    v=(v+k*las-1)%n+1;p=(p+k*las)%(s+1);
    fq(i,18,0) if(ff[i][v]&&ff1[i][v]>p) v=ff[i][v];
    printf("%d\n",dis[v]);las=dis[v];
  }
}

在上述提高组操作和数据分治后，即可获得$80pts$的高分。。。

$100pts$算法

先咕着。