Sack (dsu on tree)
(tree/sack.cpp)

• View this file on GitHub
• Last update: 2020-10-14 14:10:54+09:00

できること

部分木に対するクエリを処理できる

unordered 系を使ったマージテクより定数倍が軽いことが多い

つかいかた

以下のラムダ式を実装する

• expand(v) : v を追加したときの処理
• shrink(v) : v を削除したときの処理
• query(k) : k 番目のクエリに対する処理

計算量

頂点数を $N$ として、expand, shrink が $O(N \log N)$ 回呼び出される

注意

• shrink(v) を呼ぶときは全体が初期化されるので、 expand(v) で変更した値を全て初期値にしてもよい（直前の操作のロールバックができる必要はない）
• 頂点 v の追加削除の際に複数の処理を行う必要がある場合は、v の子としてダミーの頂点を追加するとよい

参考リンク

[Tutorial] Sack (dsu on tree)

Verified with

• test/aoj/2995.test.cpp

Code

#ifndef call_from_test
#include <bits/stdc++.h>
using namespace std;
#endif

//BEGIN CUT HERE
struct Sack{
  using F = function<void(int)>;

  vector<int> sub,hvy,big;
  vector< vector<int> > G,Q;
  F expand,shrink,query;

  Sack(int n,F expand,F shrink,F query):
    sub(n,1),hvy(n,-1),big(n,0),G(n),Q(n),
    expand(expand),shrink(shrink),query(query){}

  void add_edge(int u,int v){
    G[u].emplace_back(v);
    G[v].emplace_back(u);
  }

  void add_query(int v,int k){
    Q[v].emplace_back(k);
  }

  void add(int v,int p,int x){
    if(x==1) expand(v);
    else shrink(v);
    for(int u:G[v])
      if(u!=p and !big[u]) add(u,v,x);
  }

  void dfs(int v=0,int p=-1,bool k=0){
    for(int u:G[v])
      if(u!=p and u!=hvy[v]) dfs(u,v,0);
    if(~hvy[v]){
      dfs(hvy[v],v,1);
      big[hvy[v]]=1;
    }
    add(v,p,1);
    for(int k:Q[v]) query(k);
    if(~hvy[v]) big[hvy[v]]=0;
    if(!k) add(v,p,0);
  }

  void build(int v=0,int p=-1){
    for(int u:G[v]){
      if(u==p) continue;
      build(u,v);
      if(hvy[v]<0 or sub[hvy[v]]<sub[u]) hvy[v]=u;
      sub[v]+=sub[u];
    }
    if(p==-1) dfs(v,p);
  }
};
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
  return 0;
}
#endif

#line 1 "tree/sack.cpp"

#include <bits/stdc++.h>
using namespace std;
#endif

//BEGIN CUT HERE
struct Sack{
  using F = function<void(int)>;

  vector<int> sub,hvy,big;
  vector< vector<int> > G,Q;
  F expand,shrink,query;

  Sack(int n,F expand,F shrink,F query):
    sub(n,1),hvy(n,-1),big(n,0),G(n),Q(n),
    expand(expand),shrink(shrink),query(query){}

  void add_edge(int u,int v){
    G[u].emplace_back(v);
    G[v].emplace_back(u);
  }

  void add_query(int v,int k){
    Q[v].emplace_back(k);
  }

  void add(int v,int p,int x){
    if(x==1) expand(v);
    else shrink(v);
    for(int u:G[v])
      if(u!=p and !big[u]) add(u,v,x);
  }

  void dfs(int v=0,int p=-1,bool k=0){
    for(int u:G[v])
      if(u!=p and u!=hvy[v]) dfs(u,v,0);
    if(~hvy[v]){
      dfs(hvy[v],v,1);
      big[hvy[v]]=1;
    }
    add(v,p,1);
    for(int k:Q[v]) query(k);
    if(~hvy[v]) big[hvy[v]]=0;
    if(!k) add(v,p,0);
  }

  void build(int v=0,int p=-1){
    for(int u:G[v]){
      if(u==p) continue;
      build(u,v);
      if(hvy[v]<0 or sub[hvy[v]]<sub[u]) hvy[v]=u;
      sub[v]+=sub[u];
    }
    if(p==-1) dfs(v,p);
  }
};
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
  return 0;
}
#endif

Back to top page