백준 30691 - 슈퍼 트리 뽀개기 (C++)

문제

• 문제 링크

  
   BOJ 30691 - 슈퍼 트리 뽀개기 
  

• 문제 요약

$N$개의 정점으로 이루어진 트리가 주어진다.
어떤 정점을 대상으로 작업을 진행할 때, 그 정점을 루트로 하는 서브트리에서 거리가 $K$ 이하인 모든 정점들이 함께 뽀개진다고 한다.

한 번의 작업만 수행할 수 있을 때 최대한 많은 정점을 뽀개는 경우를 찾아보자.


• 제한

TL : $2$ sec, ML : $1024$ MB




$1 ≤ N ≤ 10^5$

$1 ≤ K ≤ 10^{18}$

$1 ≤weight ≤ 10^9$

알고리즘 분류

• 자료 구조 (data_structures)
• 트리 (trees)
• 세그먼트 트리 (segtree)
• 머지 소트 트리 (merge_sort tree)
• 오일러 경로 테크닉 (euler_tour technique)

풀이

트리 문제를 풀 때, 종종 "이 문제를 선형에서 푼다면$?$" 이라는 생각을 해보는 것이 도움이 될 때가 있다.

이 문제를 선형 구조에서 푼다고 생각해보자.

이는 곧 이 문제 와 본질적으로 같다.

세그먼트 트리에서, 노드마다 관리하는 구간의 정보를 정렬된 상태로 들고 있다고 해보자.

그럼 각 구간에서 $K$보다 크거나 작은 요소들의 개수를 이분 탐색을 이용해 $O(logN)$에 찾을 수 있으므로 쿼리당 $O(log^2N)$에 문제를 풀 수 있다.

---

다시 이번 문제로 돌아와서, 쿼리의 적용 구간을 보자.

일반적인 경로상 쿼리가 아니라 어떤 정점 $u$의 서브트리에만 쿼리가 적용된다.

따라서, $ETT$로 적절한 $ordering$을 해준다면 서브트리로의 쿼리 범위를 $[in[u], out[u]]$로 처리할 수 있다.

$dist[u]$ : $1$번 정점으로부터 $u$번 정점까지의 거리.

위 값을 가지고 $merge$_$sort$ $tree$를 구성하자.

이제 모든 정점에서 쿼리를 날려보며 최댓값을 찾아주면 될테고, 이 경우 문제를 $O(Nlog^2N)$에 풀 수 있을 것이다.

정점 $u$에 쿼리를 날릴 때, 그 서브트리에 속한 정점들의 $dist$는 기본적으로 $dist[u]$만큼 증가된 상태이다.

따라서 단순히 $K$로만 대상을 설정하면 안되고, $K+dist[u]$로 설정해주어야 한다.

---

난 이 풀이 방식이 먼저 보여서 이렇게 풀었는데, 이후 기여창을 들어가보니 다양한 풀이가 존재해 보였다.

$sparse$_$table$ $+$ $imos$나 $small$_$to$_$large$로도 풀 수 있다고 한다.

전자의 방식은 좀 더 어려운 풀이같고, 후자의 방식이 제일 간단하고 효율적인 풀이 방식일 것 같다.

리프 정점부터 거리의 최댓값을 가지고 허용 범위 내에서 집합을 묶어주며 올라오면, 약 $O(NlogN)$에 문제를 풀 수 있을 듯 하다.

전체 코드

#include<bits/stdc++.h>
using ll = long long;
using namespace std;
 
const int MAXN(1e5 + 5);
 
vector <pair<int, int>> tree[MAXN];
vector <ll> seg[1 << 18];
 
int in[MAXN], out[MAXN];
ll dist[MAXN];
 
ll n, k, cur;
void ETT(int now, ll cost)
{
    dist[now] = cost;
    in[now] = ++cur;
    for (auto& [nxt, weight] : tree[now])
        if (!in[nxt])
            ETT(nxt, cost + weight);
    out[now] = cur;
}
void update(int n, int s, int e, int i, ll val)
{
    if (s > i || e < i) return;
    seg[n].push_back(val);
    if (s ^ e)
    {
        int m(s + e >> 1);
        update(n << 1, s, m, i, val);
        update(n << 1 | 1, m + 1, e, i, val);
    }
}
int query(int n, int s, int e, int l, int r, ll add)
{
    if (s > r || e < l) return 0;
    if (s >= l && e <= r)
        return upper_bound(seg[n].begin(), seg[n].end(), k + add) - seg[n].begin();
 
    int m(s + e >> 1);
    return query(n << 1, s, m, l, r, add) + query(n << 1 | 1, m + 1, e, l, r, add);
}
void seginit()
{
    for (int i(1); i <= n; i++)
        update(1, 1, n, in[i], dist[i]);
 
    for (int i{}; i < (1 << 18); i++)
        sort(seg[i].begin(), seg[i].end());
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> k;
    for (int i{}; ++i < n;)
    {
        int u, v, w; cin >> u >> v >> w;
        tree[u].emplace_back(v, w);
        tree[v].emplace_back(u, w);
    }
 
    ETT(1, 0);
    seginit();
 
    int ans{};
    for (int i(1); i <= n; i++)
        ans = max(ans, query(1, 1, n, in[i], out[i], dist[i]));
 
    cout << ans;
}

comment

끝