题解：P14485 [集训队互测 2018] 有向图

zyn0309 · 2026-01-27 10:49:23 · 题解

\text{Link}

思路

首先这是一个保序回归问题，如果没有了解过可以查询一下论文。

我们把有向边看成无向边来建图。

对于树的情况，因为偏序关系是 \le，最后的 d 一定再初始的 d 序列中。设 f_{i,j} 为 i 的子树内，全部满足顺序，d_i 为原序列中第 j 小的最小代价。

从一个子树转移过来，代价的变化是加子树 f 前缀最小值/加子树后缀最小值。

上图三条线分别表示叶子结点的 f，f 的前缀最小值，f 的后缀最小值，显然斜率都是不降的。

非叶子结点的函数就是把一堆斜率不降的函数加起来，依次斜率也是不降的。

然后我们可以直接用线段树合并维护 slope trick，但是这个东西扩展到基环树需要多带一个 \log n，考虑使用论文里面保序回归问题整体二分的方法。

算法流程如下，我们先钦定点 d_i 为 i 所在整体二分区间的 mid 或 mid+1。整体二分的时候逐层处理，每层跑我们暴力的那个 DP，但是第二维只会取 mid 或 mid+1，如果 mid 更优就把 i 放到左边，否则把 i 放到右边。整体二分的正确性容易由斜率的单调看出，时间复杂度 O(n \log n)。

现在考虑如何扩展到基环树，找出环上的一条边 x \to y 并把它断开，并令 x 为根。

之后还是类似前面整体二分的流程来跑，只要先钦定 d_y=mid，再钦定 d_y=mid+1 跑两遍，取答案小的就可以了。

时间复杂度 O(n \log n)，较为卡常。

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii  pair<int,int>  
#define pb emplace_back
const int N=3e5+10;
int n,m,len,a[N],limit,val[N][2],p[N][2][2],w[N],to[N],vy,x,y,L[N],R[N],fa[N],pos[N],pos2[N],cnt;
ll b[N],f[N][2];
vector<pair<int,char> >e[N];
bitset<N>vis;
inline ll myABS(ll x){return (x>=0)?x:(-x);}
inline void push(int c){
    to[pos2[1]]=c;
    for(int i=1;i<=n;++i){
      int u=pos2[i];
      for(pii qwq:e[u]){
        int v=qwq.first;
        if(v==fa[u])continue;
        to[v]=p[v][to[u]][vy];
      }
    }
}
inline void find(int u,int fa){
    pos[++cnt]=u;
    vis[u]=1;
    int len=e[u].size();
    for(int i=0;i<len;++i){
      int v=e[u][i].first,c=e[u][i].second;
      if(v==fa)continue;
      if(vis[v]){
        if(c)x=u,y=v;
        else x=v,y=u;
        continue;
      }
      find(v,u);
    }
}
inline void find2(int u){
    pos[++cnt]=u;
    int len=e[u].size();
    for(int i=0;i<len;++i){
      int v=e[u][i].first;
      if(v==fa[u])continue;
      find2(v);
    }
}
inline void getfa(int u){
    vis[u]=1;
    for(pii p:e[u]){
      int v=p.first;
      if(vis[v])continue;
      fa[v]=u;
      getfa(v);
    }
}
inline void solve(){
    for(int i=1;i<=n;++i){
      int u=pos[i];
      if(u==y){
        if(!vy)f[u][0]=myABS(b[val[u][0]]-b[a[u]])*w[u],f[u][1]=1e18;
        else f[u][1]=myABS(b[val[u][1]]-b[a[u]])*w[u],f[u][0]=1e18;
      }
      else{
        f[u][0]=myABS(b[val[u][0]]-b[a[u]])*w[u];
        f[u][1]=myABS(b[val[u][1]]-b[a[u]])*w[u];
      }
      int len=e[u].size();
      for(int i=0;i<len;++i){
        int v=e[u][i].first,c=e[u][i].second;
        if(fa[u]==v)continue;
        if(c){
          if(val[u][0]<=val[v][0]){
            if(f[v][0]<=f[v][1]){
              f[u][0]+=f[v][0];
              p[v][0][vy]=0;
            }
            else{
              f[u][0]+=f[v][1];
              p[v][0][vy]=1;
            }
          }
          else{
            f[u][0]+=f[v][1];
            p[v][0][vy]=1;
          }
          if(val[u][1]<=val[v][0]){
            if(f[v][0]<=f[v][1]){
              f[u][1]+=f[v][0];
              p[v][1][vy]=0;
            }
            else{
              f[u][1]+=f[v][1];
              p[v][1][vy]=1;
            }
          }
          else{
            f[u][1]+=f[v][1];
            p[v][1][vy]=1;
          }
        }
        else{
          if(val[u][0]>=val[v][1]){
            if(f[v][0]<=f[v][1]){
              f[u][0]+=f[v][0];
              p[v][0][vy]=0;
            }
            else{
              f[u][0]+=f[v][1];
              p[v][0][vy]=1;
            }
          }
          else{
            f[u][0]+=f[v][0];
            p[v][0][vy]=0;
          }
          if(val[u][1]>=val[v][1]){
            if(f[v][0]<=f[v][1]){
              f[u][1]+=f[v][0];
              p[v][1][vy]=0;
            }
            else{
              f[u][1]+=f[v][1];
              p[v][1][vy]=1;
            }
          }
          else{
            f[u][1]+=f[v][0];
            p[v][1][vy]=0;
          }
        }
      }
    }
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;++i)cin>>a[i],b[i]=a[i];
    sort(b+1,b+1+n);
    len=unique(b+1,b+1+n)-b-1;
    for(int i=1;i<=n;++i)a[i]=lower_bound(b+1,b+1+len,a[i])-b;
    for(int i=1;i<=n;++i)cin>>w[i];
    int u,v;
    for(int i=1;i<=m;++i){
      cin>>u>>v;
      e[u].pb(v,1);
      e[v].pb(u,0);
    }
    getfa(1);
    for(int i=1;i<=n;++i)L[i]=1,R[i]=len;
    vis.reset();
    find(1,0);
    for(int i=1;i<=n;++i)pos2[i]=pos[i];
    reverse(pos+1,pos+1+n);
    if(m==n-1){
      while(1){
        for(int i=1;i<=n;++i){
          if(L[i]==R[i])val[i][0]=val[i][1]=L[i];
          else{
            int mid=(L[i]+R[i])>>1;
            val[i][0]=mid,val[i][1]=mid+1;
          }
        }
        solve();
        if(f[1][0]<=f[1][1])push(0);
        else push(1);
        bool flag=0;
        for(int i=1;i<=n;++i){
          if(L[i]==R[i])continue;
          flag=1;
          int mid=(L[i]+R[i])>>1;
          if(!to[i])R[i]=mid;
          else L[i]=mid+1;
        }
        if(!flag)break;
      }
      cout<<min(f[1][0],f[1][1])<<"\n";
    }
    else{
      for(int i=0;i<(int)e[x].size();++i){
        if(e[x][i].first!=y||!e[x][i].second)continue;
        for(int j=i+1;j<(int)e[x].size();++j)
          swap(e[x][j-1],e[x][j]);
        e[x].pop_back();
        break;
      }
      for(int i=0;i<(int)e[y].size();++i){
        if(e[y][i].first!=x||e[y][i].second)continue;
        for(int j=i+1;j<(int)e[y].size();++j)
          swap(e[y][j-1],e[y][j]);
        e[y].pop_back();
        break;
      }
      fill(fa+1,fa+1+n,0);
      vis.reset();
      getfa(x);
      cnt=0;
      find2(x);
      for(int i=1;i<=n;++i)pos2[i]=pos[i];
      reverse(pos+1,pos+1+n);
      while(1){
        bool flag=1;
        for(int i=1;i<=n;++i){
          if(L[i]==R[i])val[i][0]=val[i][1]=L[i];
          else{
            flag=0;
            int mid=(L[i]+R[i])>>1;
            val[i][0]=mid,val[i][1]=mid+1;
          }
        }
        if(flag){
          solve();
          break;
        }
        ll res=1e18;
        if(val[x][0]<=val[y][0]){
          vy=0;
          solve();
          if(val[x][1]<=val[y][0]&&f[x][1]<=f[x][0]){
            res=f[x][1];
            push(1);
          }
          else{
            res=f[x][0];
            push(0);
          }
        }
        if(val[x][0]<=val[y][1]){
          vy=1;
          solve();
          if(val[x][1]<=val[y][1]&&f[x][1]<=f[x][0]){
            if(f[x][1]<res)
              push(1);
          }
          else if(f[x][0]<res)push(0);
        }
        for(int i=1;i<=n;++i){
          if(L[i]==R[i])continue;
          int mid=(L[i]+R[i])>>1;
          if(!to[i])R[i]=mid;
          else L[i]=mid+1;
        }
      }
      cout<<min(f[x][0],f[x][1])<<"\n";
    }
    return 0;
}