Prerequisite

  • Small to Large
  • HLD

Intro

이 글은 코드포스의 이 블로그 를 기반으로 작성되었다.

어떤 문제를 풀다 Tree DP로 쉽게 될 것 같은데? 라고 생각했던 값이 쉽게 구해지지 않는것에서 의아함을 느꼈고 포스팅을 작성하게 되었다.

Sack

Sack이란건 생소한데, 그냥 저 블로그 포스터가 붙인 이름인거같다.

실제 DSU를 사용하는건 아닌것같아 보이지만 Small To Large 테크닉을 이용한 트리에서의 테크닉의 한 종류라고 생각하면 된다.

다음과 같은 쿼리를 생각해보자.

트리에서 각 정점들이 임의의 정수를 가질 때, $u$의 서브트리에서 $x$ 를 값으로 가지는 정점의 개수는 몇개인가?

만약 문제에서 $x$가 고정이 되어 있다면 Tree DP로 쉽게 구할 수 있겠지만, 만약 임의의 $x$에 대해 $u$ 에서 모두 쿼리를 빠르게 날리고 싶다면 쉽지 않음을 알 수 있다.

Euler tour technic을 이용한다면 서브트리의 정점들이 연속된 구간들로 표현이 되기 때문에 $in_u \sim out_u$ 의 범위안에 있는 정점들로 다른 자료구조를 섞어서 쓰면 가능할지도(?) 이 부분은 잘 모르겠다.

어쨌든 Sack이라는 테크닉은 이러한 종류의 쿼리를 처리해주는 테크닉이라고 할 수 있다.

주의해야 할 점

첫 번째는 위에서 언급한 정수가 몇개가 있느니 하는 쿼리에 국한되지 않는다는 점이다. 일반화해서 말하자면 “$u$ 의 서브트리에 자유도 높은 쿼리를 날릴 후 있다” 정도이다.

두 번째는 알고리즘이 종료된 후에도 막 임의의 정점에 대해 원하는 쿼리를 때려버릴 수는 없다는 것이다.

아래 구현에서 설명할거지만, DFS를 진행하며 어떤 결과 자료구조를 계속해서 관리하는 방식이기 때문에 $u$ 정점을 순회하고 있을 때만 $u$ 정점에서 쿼리를 날릴 수 있다.

필요한 값이 있다면 그 때 쿼리를 하거나 그 때 저장해두는 방식으로 추후에 이용함은 당연히 가능하다.

시간복잡도

$O(n \log n)$ 이다. 트리에서 Small to large를 기반으로 동작되기 때문이다.

자료구조를 사용하면 추가 상수가 붙음에 유의

구현

원글을 참고하면 $O(n \log n)$ 이라는 세 가지 구현 방법이 나오는데, 모두 읽어봤는데 특별히 구현 난이도나 차이는 크지 않은것같아 기호에 맞게 선택해서 익히면 좋을 것 같다.

모든 dfs 함수는 다음과 같은 형태를 띈다.

void dfs(int cur, int p, bool keep) { ... }

이는 현재 정점과 부모 정점, 그리고 현재 정점에서 처리된 값을 롤백하지 않고 유지할지를 결정하는 플래그이다.

주된 아이디어는 다음과 같다. 하나의 정점을 처리할 때 다음과 같은 일들이 순차적으로 진행된다.

  1. 서브트리의 크기들을 전처리해둔다. 이를 $S$ 라고 하자.
  2. 자식 중, 가장 무거운 자식 정점을 찾고 그걸 $B$라고 하자.
    1. HLD에서 그 무거운 간선의 개념이 맞다. 가장 서브트리의 크기가 큰 자식을 의미한다.
  3. 가벼운 자식 정점은 dfs(to, cur, false) 처럼 호출을 한다.
    1. 가벼운 자식 정점으로 DFS를 돌려주고 거기서 빠져나올 때, 처리된 값을 롤백하라는 의미이다.
  4. 무거운 자식 정점은 dfs(to, cur, true) 를 호출한다.
    1. 무거운 자식 정점은 처리된 값을 롤백하지 않는다.
  5. 현재 정점의 값을 자료구조에에 업데이트한다.
  6. 가벼운 자식 정점들은 다시 그 서브트리의 정점들을 순회하며 값을 하나씩 직접 자료구조에 업데이트한다.
  7. 만약 keep=false 라면 현재 서브트리의 값을 롤백한다.

Sack 구현

Sack은 원글에서도 소개되었지만 Euler tour Technic을 이용해 각 정점마다 들어가는 시간(dfsn), 나오는 시간을 얻고 어떤 순서 $t$ 에 어떤 정점이 들어갔는지도 저장해둔다.

이 과정을 이용해 각 정점마다 서브트리에 있는 정점들의 배열을 따로 관리할 필요 없이 쉽게 정점의 서브트리의 정점들을 순회할 수 있다.

다음과 같은 문제를 보자.

풀이 코드는 다음과 같다.

  • in: ETT에서 들어가는 순서(inclusive)
  • out: ETT에서 나오는 순서(inclusive)
  • in_rev: in의 역함수
  • size: 서브트리 크기
  • c: 입력으로 들어오는 정점들의 색 $(1 \sim n)$
  • color: 어떤 색이 현재 존재하는 개수
  • sum: 현재 $k$개인 색들의 합
  • mx_sum 현재 가장 많이 나온 수의 개수
  
int mx_sum = 0;  
map<int, int> color, sum;  
auto add = [&](int x) {  
   sum[color[x]] -= x;  
   color[x]++;  
   sum[color[x]] += x;  
   mx_sum = max(mx_sum, color[x]);  
};  
auto remove = [&](int x) {  
   sum[color[x]] -= x;  
   color[x]--;  
   sum[color[x]] += x;  
   if (mx_sum == color[x] + 1 && sum[color[x] + 1] == 0)  
      mx_sum = color[x];  
};

function<void(int, int, bool)> sack = [&](int cur, int p, bool keep) -> void {  
   int B = -1;  
   for (int to: edges[cur]) {  
      if (to == p) continue;  
      if (B == -1 || size[B] < size[to]) B = to;  
   }  
  
   for (int to: edges[cur])  
      if (to != p && to != B)  
         sack(to, cur, false);  
   if (B != -1)  
      sack(B, cur, true);  
   add(c[cur]);  
  
   for (int to: edges[cur])  
      if (to != p && to != B)  
         for (int i = in[to]; i <= out[to]; i++)  
            add(c[in_rev[i]]);  
  
   ans[cur] = sum[mx_sum];  
  
   if (!keep)  
      for (int i = in[cur]; i <= out[cur]; i++)  
         remove(c[in_rev[i]]);  
};  
sack(0, -1, 1);

연습 문제

더 많은 문제는 원문 링크에서 풀어볼 수 있다.

원문에 없는 문제들을 좀 골라보자.

BOJ 25549 - 트리의 MEX

이 문제도 기본 문제이다.

MEX를 쉽게 구하는 값은 $0 \sim N-1$ 의 값을 모두 set 으로 관리하고 자료구조에 어떤 $x$가 들어오면 그 set 에서 그걸 제거한 다음 가장 작은 원소를 구하면 된다.

만약 모든 수가 있다면 set이 빌 수도 있으므로 구현의 편의성을 위해 $N$ 도 넣고 시작하자.

void solve() {  
   int n;  
   cin >> n;  
  
   vvi edges(n);  
   int root = 0;  
   for (int i = 0, p; i < n; i++) {  
      cin >> p, p--;  
      if (p >= 0) edges[p].pb(i), edges[i].pb(p);  
      if (p == -2) root = i;  
   }  
   vi c(n);  
   fv(c);  
   vi ans(n), in(n, -1), out(n), in_rev(n), size(n);  
   int dfsn = 0;  
   function<void(int)> dfs = [&](int cur) -> void {  
      size[cur]++;  
      in[cur] = dfsn++;  
      in_rev[dfsn - 1] = cur;  
      for (int to: edges[cur]) if (in[to] == -1) dfs(to), size[cur] += size[to];  
      out[cur] = dfsn - 1;  
   };  
   dfs(root);  
  
   int mx_sum = 0;  
  
   map<int, int> color;  
   set<int> MEX;  
   for (int i = 0; i <= n; i++) MEX.insert(i);  
  
   auto add = [&](int x) {  
      color[x]++;  
      if (color[x] == 1)  
         MEX.erase(x);  
   };  
   auto remove = [&](int x) {  
      color[x]--;  
      if (color[x] == 0)  
         MEX.insert(x);  
   };  
   function<void(int, int, bool)> sack = [&](int cur, int p, bool keep) -> void {  
      int B = -1;  
      for (int to: edges[cur]) {  
         if (to == p) continue;  
         if (B == -1 || size[B] < size[to]) B = to;  
      }  
  
      for (int to: edges[cur])  
         if (to != p && to != B)  
            sack(to, cur, false);  
      if (B != -1)  
         sack(B, cur, true);  
  
      add(c[cur]);  
  
      for (int to: edges[cur])  
         if (to != p && to != B)  
            for (int i = in[to]; i <= out[to]; i++)  
               add(c[in_rev[i]]);  
  
      ans[cur] = *MEX.begin();  
  
      if (!keep)  
         for (int i = in[cur]; i <= out[cur]; i++)  
            remove(c[in_rev[i]]);  
   };  
   sack(root, -1, 1);  
   for (int i = 0; i < n; i++) cout << ans[i] << '\n';  
}

이 문제는 굳이 이렇게 안구하고 정직하게 Smaller to large를 써도 되지만, 이렇게도 풀 수 있다.

참고

Comments

You may also enjoy