[BZOJ4699]树上的最短路(最短路+线段树)

https://www.cnblogs.com/Gloid/p/10273902.html

这篇文章已经从头到尾讲的非常清楚了，几乎没有什么需要补充的内容。

首先$O(n\log^2 n)$的做法比较显然，倍增优化建图+最短路即可。

然后利用“每个塌陷最多会被使用一次”的性质，为每个塌陷（边也看作一种塌陷）建一个点跑一个变体的Dijkstra就可以优化到$O((n+m)\log n)$。

这里讲下我最后一步的实现。

为每个塌陷找未标记的点很简单，并查集f[i]表示离i最近的未被标记的祖先，每次标记i后f[i]=get(fa[i])即可。

为每个点找未标记的塌陷相对复杂，分两种情况考虑。

一是x是这个塌陷的LCA，这个很好处理，开个vector存储以每个点为LCA的所有塌陷即可。

二是塌陷的一个端点在x子树内，一个在子树外。

设x的子树的DFS序区间为[L,R]

考虑每次取出“一个端点在x的子树中，另一个端点的DFS序尽量小”的未标号的塌陷，若此塌陷的另一个端点在L之前则说明这个塌陷过点x。

更新完后再把这个塌陷删掉，直到取出的塌陷在L之后。同理，对“尽量大”的塌陷也做一遍，直到这个塌陷另一个端点DFS序在R之前。

于是我们要支持的是，查询一个端点在某个区间中的所有塌陷的另一个端点最小/大值。

线段树维护每个区间中的这个信息，同时在线段树的叶子上，用堆维护“以这个点为端点的所有塌陷的另一个端点”。

由于尽量小和尽量大都要做一边，所以要开一个大根堆和一个小根堆。

实现起来可能没有什么细节，只是要注意代码不要写残，自己证一遍复杂度，否则可能不小心就写成$O(n\log^2 n)$的了。

 #include<queue>
 #include<cstdio>
 #include<algorithm>
 #define ls (x<<1)
 #define rs (ls|1)
 #define lson ls,L,mid
 #define rson rs,mid+1,R
 #define rep(i,l,r) for (int i=(l); i<=(r); i++)
 #define For(i,x) for (int i=h[x],k; i; i=nxt[i])
 typedef long long ll;
 using namespace std;

 const int N=,M=;
 ll inf=1e15;
 bool tag[M],b[M];
 ll dis[M];
 int n,m,S,u,v,w,cnt,tot,tim;
 int pos[N],f[N],L[N],R[N],dep[N],fa[N][];
 int h[N],to[N<<],nxt[N<<],mn[N<<],mn1[N<<],mx[N<<],mx1[N<<];
 struct E{ int L1,R1,L2,R2,w; }e[M];
 vector<int>ve[N];

 struct P{ int id,s; };
 bool operator <(const P &a,const P &b){ return a.s<b.s; }
 struct Cmp{ bool operator ()(const P &a,const P &b){ return a.s>b.s; } };
 priority_queue<P,vector<P>,Cmp>Q1[N];
 priority_queue<P>Q2[N];

 struct D{ int x; ll d; };
 bool operator <(const D &a,const D &b){ return a.d>b.d; }
 priority_queue<D>Q;

 void add(int u,int v){ to[++cnt]=v; nxt[cnt]=h[u]; h[u]=cnt; }
 int get(int x){ return f[x]==x ? x : f[x]=get(f[x]); }

 void dfs(int x){
     dep[x]=dep[fa[x][]]+; L[x]=++tim; pos[tim]=x;
     rep(i,,) fa[x][i]=fa[fa[x][i-]][i-];
     For(i,x) if ((k=to[i])!=fa[x][]) fa[k][]=x,dfs(k);
     R[x]=tim;
 }

 int Lca(int x,int y){
     if (dep[x]<dep[y]) swap(x,y);
     int t=dep[x]-dep[y];
     for (int i=; ~i; i--) if (t&(<<i)) x=fa[x][i];
     if (x==y) return x;
     for (int i=; ~i; i--) if (fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
     return fa[x][];
 }

 void upd(int x){
     if (mn1[ls]<mn1[rs]) mn[x]=mn[ls],mn1[x]=mn1[ls]; else mn[x]=mn[rs],mn1[x]=mn1[rs];
     if (mx1[ls]>mx1[rs]) mx[x]=mx[ls],mx1[x]=mx1[ls]; else mx[x]=mx[rs],mx1[x]=mx1[rs];
 }

 void build(int x,int L,int R){
     if (L==R){
         int p=pos[L]; mn1[x]=n+; mx1[x]=-;
         if (!Q1[p].empty()) mn[x]=Q1[p].top().id,mn1[x]=Q1[p].top().s;
         if (!Q2[p].empty()) mx[x]=Q2[p].top().id,mx1[x]=Q2[p].top().s;
         return;
     }
     int mid=(L+R)>>; build(lson); build(rson); upd(x);
 }

 void que(int x,int L,int R,int l,int r,bool k,int &s,int &s1){
     if (L==l && r==R){
         if (!k) s=mn[x],s1=mn1[x]; else s=mx[x],s1=mx1[x];
         return;
     }
     int mid=(L+R)>>;
     if (r<=mid) que(lson,l,r,k,s,s1);
     else if (l>mid) que(rson,l,r,k,s,s1);
         else{
             int a,a1,b,b1;
             que(lson,l,mid,k,a,a1); que(rson,mid+,r,k,b,b1);
             if (!k){ if (a1<b1) s=a,s1=a1; else s=b,s1=b1; }
                 else { if (a1>b1) s=a,s1=a1; else s=b,s1=b1; }
         }
 }

 void del(int x,int L,int R,int p,bool k){
     if (L==R){
         p=pos[p];
         if (!k){
             Q1[p].pop(); mn[x]=; mn1[x]=n+;
             if (!Q1[p].empty()) mn[x]=Q1[p].top().id,mn1[x]=Q1[p].top().s;
         }else{
             Q2[p].pop(); mx[x]=; mx1[x]=-;
             if (!Q2[p].empty()) mx[x]=Q2[p].top().id,mx1[x]=Q2[p].top().s;
         }
         return;
     }
     int mid=(L+R)>>;
     if (p<=mid) del(lson,p,k); else del(rson,p,k);
     upd(x);
 }

 void solve1(int x){
     int u=e[x].L2,v=e[x].R2,lca=Lca(u,v);
     u=f[u]; v=f[v];
     while (dep[u]>=dep[lca] || dep[v]>=dep[lca]){
         if (!u && !v) break;
         if (dep[u]<dep[v]) swap(u,v);
         if (!tag[u]) dis[u]=min(dis[u],dis[x+n]),Q.push((D){u,dis[u]});
         tag[u]=; u=f[u]=get(fa[u][]);
     }
 }

 void solve2(int x){
     int ed=ve[x].size()-;
     rep(i,,ed){
         int k=ve[x][i];
         if (!tag[k+n]) tag[k+n]=,dis[k+n]=min(dis[k+n],dis[x]+e[k].w),Q.push((D){k+n,dis[k+n]});
     }
     while (){
         int mn,mn1,mx,mx1;
         que(,,n,L[x],R[x],,mn,mn1);
         que(,,n,L[x],R[x],,mx,mx1);
         if (mn1>=L[x]) mn=;
         if (mx1<=R[x]) mx=;
         if (!mn && !mx) break;
         if (mn){
             if (!tag[mn+n]) dis[mn+n]=min(dis[mn+n],dis[x]+e[mn].w),Q.push((D){mn+n,dis[mn+n]});
             tag[mn+n]=; del(,,n,L[e[mn].L1]+L[e[mn].R1]-mn1,);
         }
         if (mx){
             if (!tag[mx+n]) dis[mx+n]=min(dis[mx+n],dis[x]+e[mx].w),Q.push((D){mx+n,dis[mx+n]});
             tag[mx+n]=; del(,,n,L[e[mx].L1]+L[e[mx].R1]-mx1,);
         }
     }
 }

 void Dij(){
     rep(i,,n+tot) dis[i]=inf; dis[S]=; Q.push((D){S,}); tag[S]=;
     while (!Q.empty()){
         int x=Q.top().x; Q.pop();
         if (b[x]) continue;
         b[x]=;
         if (x>n) solve1(x-n); else solve2(x);
     }
 }

 int main(){
     freopen("bzoj4699.in","r",stdin);
     freopen("bzoj4699.out","w",stdout);
     scanf("%d%d%d",&n,&m,&S);
     rep(i,,n) scanf("%d%d%d",&u,&v,&w),e[++tot]=(E){u,u,v,v,w},e[++tot]=(E){v,v,u,u,w},add(u,v),add(v,u);
     dfs();
     rep(i,,n) f[i]=i;
     rep(i,,m) tot++,scanf("%d%d%d%d%d",&e[tot].L2,&e[tot].R2,&e[tot].L1,&e[tot].R1,&e[tot].w);
     rep(i,,tot){
         int u=e[i].L1,v=e[i].R1,lca=Lca(u,v);
         ve[lca].push_back(i);
         Q1[u].push((P){i,L[v]}); Q2[u].push((P){i,L[v]});
         Q1[v].push((P){i,L[u]}); Q2[v].push((P){i,L[u]});
     }
     build(,,n); Dij();
     rep(i,,n) printf("%lld\n",dis[i]);
     return ;
 }