[eJOI2022] Bounded Spanning Tree 题解

FFTotoro · 2025-08-29 10:18:32 · 题解

一年半之前的模拟赛原题。

从部分分 m=n-1 出发，问题转换为确定一个长度为 m 的排列 w_1,w_2,\ldots,w_m，满足 w_i\in[l_i,r_i]。这是一个非常经典的贪心：考虑依次确定值为 1,2,\ldots,m 的位置，每次取出 l_i 最小的 i，若有多个 i 满足条件取 r_i 最小的，令 w_i 为当前的值。这个过程可以优先队列维护；若过程中出现了 w_i 不满足条件的情况，那么问题必然无解。

现在考虑如何使前 n-1 条边组成最小生成树。首先建出这棵树 T；令第 i 条边为 e_i，由于边权互不相同，所以对于一条不在 T 上的边 e_i=(u,v)(i\ge n)，它的权值必然大于 T 上 u\leftrightarrow v 路径上所有边权的最大值。

尝试进行一些操作：设 u\leftrightarrow v 路径上的边分别为 e_{p_1},e_{p_2},\ldots,e_{p_k}，可以令 l_i\gets\max\left\{l_i,\left(\max\limits_{j=1}^kl_{p_j}\right)+1\right\}（操作一），并且对于路径上每一条边 e_{p_j} 令 r_{p_j}\gets\min\left\{r_{p_j},r_i-1\right\}（操作二）。

根据最小生成树的性质可知，这样做仅仅筛掉了一些不合法的解，并不会把正确的解判漏；但是据此可以观察到一个非常有用的性质：进行完所有操作之后，对于所有不在 T 上的边 e_i=(u,v) 和 T 上 u\leftrightarrow v 路径包含的某条边 e_j，都满足 l_i>l_j\land r_i>r_j！这意味着如果执行最开始的贪心流程，最终必然有 w_i>w_j，满足条件。

直接模拟上面的流程，操作一使用树剖 + ST 表维护链上最大值，操作二可以按照 r_i 从小到大覆盖到链上（转换为区间覆盖后用并查集维护）。令 n,m 同阶，时间复杂度为 O(n\log n)。

放代码：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tpi;
typedef tuple<int,int,int,int> edge;
namespace IAOI_lib{
  class dsu{
    private:
      vector<int> a;
    public:
      dsu(int n):a(n){
        iota(a.begin(),a.end(),0);
      }
      int leader(int x){
        return a[x]==x?x:a[x]=leader(a[x]);
      }
      void merge(int x,int y){
        x=leader(x),y=leader(y);
        if(x!=y)a[x]=y;
      }
  }; // 并查集模板
  template<typename T,T(*op)(T,T)> class sparse_table{
    private:
      vector<vector<T> > s;
    public:
      sparse_table(vector<T> a){
        int k=__lg(a.size());
        s.resize(k+1,vector<T>(a.size()));
        for(int i=0;i<a.size();i++)
          s[0][i]=a[i];
        for(int i=1;i<=k;i++)
          for(int j=0;j+(1<<i)<=a.size();j++)
            s[i][j]=op(s[i-1][j],s[i-1][j+(1<<i-1)]);
      }
      T query(int l,int r){
        int k=__lg(r-l+1);
        return op(s[k][l],s[k][r-(1<<k)+1]);
      }
  }; // ST 表模板
}
vector<int> cover(int n,vector<tpi> v){
  vector<int> f(n,-1);
  IAOI_lib::dsu d(n);
  for(auto [l,r,c]:v)
    for(int i=l;i<=r;i++){
      if(~f[i])i=d.leader(i);
      else if(f[i]=c;i<n-1&&(i<r||~f[i+1]))d.merge(i,i+1);
    }
  return f;
} // 区间覆盖（P2391），使用并查集维护
inline int mx(int x,int y){return x>y?x:y;}
class hld{
  private:
    int n;
    vector<vector<tpi> > g;
    vector<int> f,d,e,h,t,l;
    vector<tpi> q;
    optional<IAOI_lib::sparse_table<int,mx> > s;
  public:
    hld(vector<vector<tpi> > g)
      :n(g.size()),g(g),f(n),d(n),e(n,1),h(n,-1),t(n),l(n){
      auto dfs=[&](auto &&self,int u)->void{
        int mx=0;
        for(auto [i,p,w]:g[u])
          if(i!=f[u]){
            f[i]=u,d[i]=d[u]+1;
            self(self,i),e[u]+=e[i];
            if(e[i]>mx)mx=e[i],h[u]=i;
          }
      };
      int o=0;
      vector<int> lv(n);
      auto decomp=[&](auto &&self,int u,bool b)->void{
        t[u]=b?t[f[u]]:u,l[u]=o++;
        if(~h[u])self(self,h[u],true);
        for(auto [i,p,w]:g[u])
          if(i!=f[u]){
            if(i!=h[u])self(self,i,false);
            lv[l[i]]=w;
          }
      };
      f[0]=-1,dfs(dfs,0),decomp(decomp,0,false);
      s.emplace(lv);
    }
    int query(int u,int v,int c){
      int w=-1;
      auto go=[&](int l,int r){
        if(l>r)return;
        w=max(w,s->query(l,r));
        q.emplace_back(l,r,c);
      };
      while(t[u]!=t[v]){
        if(d[t[u]]>d[t[v]])swap(u,v);
        go(l[t[v]],l[v]),v=f[t[v]];
      }
      if(d[u]>d[v])swap(u,v);
      return go(l[u]+1,l[v]),w;
    } // 一条非树边造成的影响
    vector<int> get_r(){
      auto r=cover(n,q);
      vector<int> rs(n-1);
      auto dfs=[&](auto &&self,int u)->void{
        for(auto [i,p,w]:g[u])
          if(i!=f[u])rs[p]=r[l[i]],self(self,i);
      };
      return dfs(dfs,0),rs;
    } // 求解所有操作二过后的 r
}; // 树剖模板
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int t; cin>>t;
  while(t--){
    int n,m; cin>>n>>m;
    vector<edge> e(m);
    for(auto &[u,v,l,r]:e)
      cin>>u>>v>>l>>r,u--,v--,l--,r--;
    vector<vector<tpi> > t(n);
    vector<int> lv(n-1);
    for(int i=0;i<n-1;i++){
      auto [u,v,l,r]=e[i];
      lv[i]=l;
      t[u].emplace_back(v,i,l);
      t[v].emplace_back(u,i,l);
    }
    hld h(t);
    vector<int> p(m);
    iota(p.begin(),p.end(),0);
    sort(p.begin(),p.end(),[&](int x,int y){
      return get<3>(e[x])<get<3>(e[y]);
    }); // 按照 r 排序，方便操作二
    for(int i:p){
      if(i<n-1)continue;
      auto &[u,v,l,r]=e[i];
      l=max(l,h.query(u,v,r)+1);
    } // 枚举非树边进行操作
    auto rs=h.get_r();
    for(int i=0;i<n-1;i++){
      auto &[u,v,l,r]=e[i];
      if(~rs[i])r=min(r,rs[i]-1);
    }
    bool f=true;
    vector<tpi> c(m);
    for(int i=0;i<m&&f;i++){
      auto [u,v,l,r]=e[i];
      if(l>r||l>=m||r<0)f=false;
      c[i]=make_tuple(l,r,i);
    }
    sort(c.begin(),c.end());
    priority_queue<pii,vector<pii>,greater<> > q;
    vector<int> w(m);
    for(int i=0,p=0;i<m&&f;i++){
      while(p<m&&get<0>(c[p])==i){
        auto [l,r,i]=c[p++];
        q.emplace(r,i);
      }
      if(q.empty()||q.top().first<i)f=false;
      else w[q.top().second]=i,q.pop();
    } // 贪心求解排列 w 的过程
    if(f){
      cout<<"Yes\n";
      for(int i:w)cout<<i+1<<' ';
      cout<<'\n';
    }
    else cout<<"No\n";
  }
  return 0;
}