BOJ 4002 - 닌자배치

문제 태그 : https://www.acmicpc.net/problem/4002

문제 태그

Segment Tree

문제 소개

문제를 이해하기가 굉장히 어려웠다. 간단하게 설명을 하자면 트리에서 임의의 노드 x를 고른다. 그 후 x의 서브트리에서 몇 개의 노드를 고른다. 이때 노드의 비용의 합이 m이하가 되게 골라야 한다. 이때 고른 노드의 갯수와 x의 가중치의 곱의 최댓값을 구하는 문제이다. 

문제 풀이

관찰 1.
x가 정해진 상황에서 x의 서브트리에서 어떤 노드들을 골라야 할 때 결국은 갯수만 중요하기 때문에 당연하게도 비용이 낮은 것부터 선택을 해야한다. 즉 greedy 하게 고를 수 있다는 것이다. 이를 바꿔서 생각하면 비용이 많은 것부터 사용하지 않을 것이다.

관찰 2.
이를 트리의 노드 사이의 관계로 확장을 시켜보자. 어떤 노드 x와 그의 부모노드 p가 있다. x가 메인일때 고른 노드들과 p가 메인일때 고른 노드들은 어떠한 관계가 있을까? p가 메인일때 고를 수 있는 노드 들은 x의 서브트리에다가 추가로 몇 개의 선택지가 추가된 것이다. 따라서 x일때 선택했던 것 중에서도 비용이 정말 작은 애들만 계속 살아남을 수 있다는 것이다. 즉, x일때 선택하지 않은 노드들은 절대 p에서 선택을 하지 않게 된다. 
따라서 어떤 노드에 대한 후보군은 그 자식노드에서 선택을 했던 노드 + 자신 중에서 선택을 하면 된다.

관찰 2.5
어떤 문제를 풀 때도 중요하지만 항상 한번쯤은 뒤집어서 생각을 해봐야 한다. 각 노드를 보면서 어떤 노드들을 선택할지를 판별하는 방식으로 알고리즘을 짜면 한 노드는 최대 n번 선택 될 수 있기 때문에 시간복잡도가 커지게 된다. 하지만 어떤 노드를 더이상 선택하지 않을 지를 중점적으로 놓고 보면, 한 노드는 최대 한 번 제외되면 이후로는 고려를 안해도 되기 때문에 시간복잡도를 확실히 줄일 수 있다.

풀이
항상 우리는 부모 노드보다 자식 노드를 먼저 봐야한다. 이 경우에는 dfs한번을 돌려서 각 노드별 깊이를 구한 다음에 정렬을 한 번 하는 것으로 순서를 해결할 수 있다. 
dfs ordering tree(euler tour tree)로 세그먼트 트리를 만든다. 이 세그먼트 트리의 역할은 단 한가지이다. 특정노드의 서브트리에서 가장 비용이 큰 값과 그 노드를 찾아내는 역할을 해준다. 나머지 모든 값들은 그냥 배열을 통해서 관리를 할 수 있다.
위에서 정렬을 한 순서대로 각 노드에서는 다음과 같은 행동을 한다.
1.  그 노드의 서브트리에서 선택할 수 있는 모든 노드의 비용의 합을 확인한다.
2. 1번의 값이 m이하로 떨어질때까지 세그먼트 트리에서 구간 최댓값을 구해서 그 위치의 값을 0으로 만든다. 이 과정에서 현재 노드가 담당하고 있는 비용의 합, 선택할 수 있는 갯수등을 개속 변화시켜준다. 
3. 2번과정이 끝났다면 당연히 남은 모든 노드를 선택할 것이다. 따라서 관리하고 있었던 값인 서브트리에서 선택할 수 있는 갯수의 값과 현재 노드의 가중치를 곱해서 답과 max를 취해준다.
4. 현재 노드가 담당하고 있는 비용의 합, 선택할 수 있는 갯수등의 관리하고 있었던 값을 그대로 부모노드에 더해준다.

3번에서 얻은 값이 그 노드를 매니저로 선택했을 때 얻는 최댓값이며, 이중 전체 최대가 정답이 된다.또한, 위와 같은 일련의 과정에서 2번의 과정을 통해 선택하지 않을 노드를 계속 걸러내는 작업을 하며, 값도 바꿔주기 때문에 이는 각 값에 대해서 최대 한 번 진행된다. 따라서 총 시간복잡도 $O(NlgN)$으로 문제를 해결할 수 있다.

코드

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pii;
 
#define ff first
#define ss second
#define ep emplace_back
#define eb emplace
#define pb push_back
 
ll vis[1010101];
ll dep[1010101];
ll in[1010101];
ll out[1010101];
vector<ll> v[1010101];
ll c[1010101];
ll le[1010101];
pii tree[1010101];
ll siz[1010101];
ll sum[1010101];
ll arr[1010101];
ll par[1010101];
 
pii upt(ll idx,ll val,ll s,ll e,ll nod){
    if(idx<s||idx>e) return tree[nod];
    if(s==e){
        tree[nod].ff=val;
        tree[nod].ss=idx;
        return tree[nod];
    }
    return tree[nod]=max(upt(idx,val,s,(s+e)/2,nod*2),upt(idx,val,(s+e)/2+1,e,nod*2+1));
}
 
pii sol(ll l,ll r,ll s,ll e,ll nod){
    if(r<s||e<l) return {0,0};
    if(l<=s&&e<=r) return tree[nod];
    return max(sol(l,r,s,(s+e)/2,nod*2),sol(l,r,(s+e)/2+1,e,nod*2+1));
}
 
ll tree2[1010101];
 
ll cnt=-1;
void dfs(ll x){
    cnt++;
    in[x]=cnt;
    vis[x]=1;
    for(auto k:v[x]){
        dep[k]=dep[x]+1;
        dfs(k);
    }
    out[x]=cnt;
}
 
bool sf(ll a,ll b){
    return dep[a]>dep[b];
}
 
int main(){
   ll i,j,k,l,m,n;
    scanf("%lld %lld",&n,&m);
    for(i=1;i<=n;i++){
        ll a;
        scanf("%lld %lld %lld",&par[i],&c[i],&le[i]);
        v[par[i]].pb(i);
        arr[i]=i;
        siz[i]=1;
        sum[i]=c[i];
    }
    dfs(0);
    for(i=1;i<=n;i++)
        upt(in[i],c[i],1,n,1);
 
    sort(arr+1,arr+1+n,sf);
    ll ans=0;
    for(i=1;i<=n;i++){
        ll x=arr[i];
        while(sum[x]>m){
            pii p=sol(in[x],out[x],1,n,1);
            sum[x]-=p.ff;
            siz[x]--;
            upt(p.ss,0,1,n,1);
        }
        ans=max(ans,le[x]*siz[x]);
        siz[par[x]]+=siz[x];
        sum[par[x]]+=sum[x];
    }
 
    printf("%lld",ans);
 
}