[COCI 2024/2025 #5] 树树 2 / Stablo II 题解

FFTotoro · 2025-02-19 23:03:51 · 题解

最朴素的做法是树剖 + 线段树维护，时间复杂度 O(n\log^2n)，需要较优秀的常数以通过。

如果我们将所有操作反转（即从后往前做），一条边被覆盖一次后就不用再被考虑，于是可以使用并查集维护，时间复杂度 O(n\log n\alpha(n))。

倒着做的思路启发了我们，能否不使用树剖？有一个很直接的想法，对于一组询问 (u,v) 直接暴力跳祖先，跳的过程中将整条路径缩成一个点（可以用并查集维护），于是可以做到 O(n\alpha(n))。实现时有一些细节，具体可以参考代码。

放代码：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
namespace IAOI_lib{
  template<typename T> class dsu{
    private:
      vector<T> a;
      vector<int> s;
    public:
      dsu(int n=2e5){
        a.resize(n),s.resize(n,1);
        iota(a.begin(),a.end(),0);
      }
      T leader(T x){
        return a[x]==x?x:a[x]=leader(a[x]);
      }
      inline int size(T x){
        return s[leader(x)];
      }
      inline void merge(T x,T y){
        x=leader(x),y=leader(y);
        if(x==y)return;
        if(s[x]>s[y])swap(x,y);
        s[y]+=s[x],a[x]=y;
      }
      inline bool same(T x,T y){
        return leader(x)==leader(y);
      }
  };
}
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n,q; cin>>n>>q;
  vector<vector<pii> > g(n);
  vector<int> r(n-1,-1),f(n),w(n),l(n);
  // r[i] 表示第 i 条边的答案，f[u] 表示 u 的父亲
  // w[u] 表示 u 到父亲的边的编号，l[u] 表示 u 的深度
  for(int i=0;i<n-1;i++){
    int u,v; cin>>u>>v;
    g[--u].emplace_back(--v,i);
    g[v].emplace_back(u,i);
  }
  auto dfs=[&](auto &&self,int u)->void{
    for(auto [i,x]:g[u])
      if(i!=f[u])l[i]=l[f[i]=u]+1,w[i]=x,self(self,i);
  }; // 预处理初始信息
  dfs(dfs,0);
  vector<pii> a(q);
  for(auto &[u,v]:a)cin>>u>>v,u--,v--;
  IAOI_lib::dsu<int> d(n);
  auto cp=[&](int x,int y){
    f[x]=f[y],w[x]=w[y],l[x]=l[y];
  }; // 并查集中的代表元发生变化，将后者的信息转换到前者便于维护
  for(int i=q-1;~i;i--){
    auto [u,v]=a[i];
    u=d.leader(u),v=d.leader(v);
    while(u!=v){
      if(l[u]>l[v]){
        int x=d.leader(f[u]);
        r[w[u]]=i,d.merge(u,x);
        if(d.leader(x)==u)cp(u,x);
        else u=x;
      } // 选深度大的跳
      else{
        int x=d.leader(f[v]);
        r[w[v]]=i,d.merge(v,x);
        if(d.leader(x)==v)cp(v,x);
        else v=x;
      }
      u=d.leader(u),v=d.leader(v);
    }
  }
  for(int i:r)cout<<i+1<<' ';
  cout<<endl;
  return 0;
}