BOJ 3319 - 전령들 (D3)

http://boj.kr/3319

#CHT #LiChaoTree #rollback

첫 D3이자 첫 자력솔 D3이다.

그런데 구현을 곁들인

3319번: 전령들

 

convex hull trick (by li chao tree) + rollback

풀이가 선뜻 생각나지 않는 이유는, 트리에서 CHT를 해야하기 때문이다.

그래도 일단 dp 식을 세워보자.

dp[i] := i번에서 1번까지 가는데 걸리는 최소 시간

 

i에서 1번으로 갈때는, i -> 1 경로 사이에 있는 어떠한 정점 j에 대하여 (즉, i의 조상)

( i에서 j까지의 경로에서 전령 i를 이용하는데 걸리는 시간 ) + (j에서 1까지 가는데 드는 최소 시간)

따라서

$$ dp[i] = min(dp[j] + ( dis(i)-dis(j) ) * V[i])+S[i] $$ 

이때 dis(k)는 1번에서 k번까지 가는데 드는 간선의 가중치만 더한 값이다.

 

이제 이 식을 CHT에 맞게 변형하면

$$ min(-dis(j) * V[i] + dp[j]) + S[i] + dis(i) * V[i] $$

여기까진 쉽다. (-dis(j)가 단조성을 띈다. 하지만 생각하기 귀찮으니 li-chao tree를 사용할 것이다.)

하지만 문제는 여기가 트리라는 것이다.

예제에서 정점과 간선만 나타낸 그림이다.

 

위 그래프에서 dfs 순서로 dp를 계산한다고 해보자.

 

먼저 1번 직선 y =0x + 0을 넣는다.

먼저 dp[2]를 계산하고, 2번 정점에서의 직선 y = -dis(2)*x+dp[2]를 넣는다.

또 dp[3]을 계산하고, 3번 정점에서의 직선 y = -dis(3)*x+dp[3]을 넣는다.

dp[4]를 계산하고 4번 정점에서의 직선 y = -dis(4)*x+dp[4]를 넣는다.

dp[5]를 계산하고 5번 정점에서의 직선 y = -dis(5)*x+dp[5]를 넣는다.

 

끝?

 

 

 

 

 

 

당연히 아니다. 위 풀이의 문제점을 찾아보자.

dp[4]를 계산할때를 주목하자. dp[4]를 계산할 때는, CHT상에 1번 직선, 2번 직선, 3번 직선이 들어있다. 그런데 실제로 dp[4]를 계산할 때는, 1번, 2번 직선만 이용해야 한다. 왜냐하면 4번에서 1번까지 올라가는 경로는 4->2->1이므로 3이 들어있지 않기 때문이다.

 

그렇다면 3번 직선을 빼주어야 하는데, 어떻게 해야 할까? 즉 직선을 어떤 순서로 빼주어야 할까?

힌트를 얻기 위해서 순서를 바꿔보자.

ctrl+v

 

여기서 3번을 먼저 방문한 것이 아닌, 4번부터 방문했다고 가정하자.

그러면 1 -> 2 -> 4 -> 5 -> 3 순서로 dfs 방문이 일어나게 된다.

 

* 4번 직선을 계산할 때에는, 1,2번 직선이 필요하다

* 5번 직선을 계산할 때에는, 1,2,4번 직선이 필요하다

* 3번 직선을 계산할 때에는, 1,2번 직선이 필요하다

 

dfs의 재귀적 성질을 이용하면, i번 직선은 i의 서브트리에 속하는 노드들을 계산할 때 이용됨을 알 수 있다. 따라서 i번 직선을 추가하고, i번에서의 dfs가 마무리되었을 때(백트랙해야할 때) i번 직선을 빼주면 된다.

 

이때 i번 직선을 빼야하는 상황이라면 그 아래의 직선들이 모두 빠진 상황이다.

즉, i번 직선은 가장 최근에 들어간 직선인 상황이므로 스택을 이용하여 구현할 수 있다. (Last in First out)

 

그렇다면 남은건 하나다. 어떻게 li-chao tree 상에서 가장 최근 직선을 빼는 작업을 진행할까?

struct Line{
    ll a,b;
    ll f(ll x){ return a*x+b; }
};
Line max(Line a, Line b, ll x){ return a.f(x) >= b.f(x) ? a : b; }
Line min(Line a, Line b, ll x){ return a.f(x) < b.f(x) ? a : b; }
struct asdf{
    ll l, r, s, e;
    Line line;
};
struct li_chao{
    vector<asdf> tree;
    void init(ll s, ll e){
        tree.push_back({-1,-1,s,e,{0,-inf}});
    }
    void upd(ll node, Line cur){
        ll s = tree[node].s, e = tree[node].e;
        ll mid = s+e>>1;
        Line low = min(tree[node].line, cur, s), high = max(tree[node].line, cur, s);
        if(low.f(e) <= high.f(e)){
            tree[node].line = high;
            return;
        }
        if(low.f(mid) < high.f(mid)){   //mid기준 오른쪽에 교점
            tree[node].line = high;
            if(tree[node].r == -1){
                tree[node].r = tree.size();
                tree.push_back({-1, -1, mid+1, e, {0,-inf}});
            }
            upd(tree[node].r, low);
        }
        else{
            tree[node].line = low;
            if(tree[node].l == -1){
                tree[node].l = tree.size();
                tree.push_back({-1,-1,s,mid,{0,-inf}});
            }
            upd(tree[node].l, high);
        }
    }
    ll query(ll node, ll x){
        if(node == -1)return -inf;
        ll s = tree[node].s, e = tree[node].e;
        ll mid = s+e>>1;
        if(x<=mid)return max(tree[node].line.f(x), query(tree[node].l, x));
        else return max(tree[node].line.f(x), query(tree[node].r, x));
    }
};

 

리차오 트리 구조체 코드이다.

새로 들어오는 직선에 의해 기존 직선이 변화하는 구간은 tree[node]가 변하는 코드(또는 tree에 push_back되는 코드)이다. 

Dynamic Segment Tree 특성상, 한번 업데이트 시 직선이 최대 O(logN)번만 업데이트된다.

 

따라서 리차오상에서 그냥 변하는 모든 정점을 스택에 넣고, rollback할 때 꺼내서 그 정점을 삭제하거나, 값만 바꿔주면 된다.

 

 

 

 

#include <iostream>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cstring>
#include <vector>
#include <string>
#include <climits>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <bitset>
#include <cassert>
#include <list>
using namespace std;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 998244353
typedef long long ll;
const ll inf1 = 2e9, inf2 = 2e18;
struct Line{	//y = ax+b
    ll a,b;
    ll f(ll x){return a*x+b;}
};
Line max(Line a, Line b, ll x){	//두 직선의 함숫값중 큰 직선
    return a.f(x) >= b.f(x) ? a : b;
}
Line min(Line a, Line b, ll x){	//두 직선의 함숫값중 작은 직선
    return a.f(x) < b.f(x) ? a : b;
}
struct Node{	//리차오
    int l,r;
    ll s,e;
    Line line;
};
struct asdf{	//롤백할 때 쓰는 구조체
    int x;
    Node before;
    int num;
};
ll n;
struct seg{
    vector<Node> tree;
    void init(ll s, ll e){
        tree.push_back({-1,-1,s,e,{0,inf2}});
    }
    stack<asdf> changed;
    inline void upd(ll node, Line k, int num){
        auto push = [&](int x, Node a, int c) -> void {	//"x번 직선을 업데이트했을 때, tree[c]는 원래 a였는데 변화했다"라는 사실 기록
            changed.push({x,a,c});
        };
        ll s = tree[node].s, e = tree[node].e;
        Line low = min(tree[node].line, k, s), high = max(tree[node].line, k, s);
        if(low.f(e) <= high.f(e)){	//구간상에서 교점이 없다
            auto cur = tree[node];
            tree[node].line = low;
            push(num, cur, node);	
            return;
        }
        ll mid = s+e>>1;
        if(low.f(mid) < high.f(mid)){	//중간보다 뒤에서 교점
            auto cur = tree[node];
            tree[node].line = low;
            push(num, cur, node);
            if(tree[node].r == -1){
                push(num, {-2,-2,-2,-2,{-2,-2}}, tree.size());	//-2 : 원래 없었던 정점
                tree[node].r = tree.size();
                tree.push_back({-1,-1,mid+1,e,{0,inf2}});
            }
            upd(tree[node].r, high, num);
        }
        else{
            auto cur = tree[node];
            tree[node].line = high;
            push(num, cur, node);
            if(tree[node].l == -1){
                push(num, {-2,-2,-2,-2,{-2,-2}}, tree.size());
                tree[node].l = tree.size();
                tree.push_back({-1,-1,s,mid,{0,inf2}});
            }
            upd(tree[node].l, low, num);
        }
    }
    inline ll query(ll node, ll x){
        if(node==-1)return inf2;
        ll s = tree[node].s, e = tree[node].e;
        ll mid = s+e>>1;
        if(x<=mid)return min(tree[node].line.f(x), query(tree[node].l, x));
        return min(tree[node].line.f(x), query(tree[node].r, x));
    }
    inline void rollback(ll X){
        while(changed.size()){
            auto [x,a,i] = changed.top();
            if(x!=X)break;
            changed.pop();
            if(a.l==-2){	//원래 없었던 정점이면 지우기
                tree.pop_back();
            }
            else tree[i] = a;	//아니면 값만 되돌리기
        }
    }
} seg;
bool visited[101010];
vector<pair<int,ll>> adj[101010];
ll dp[101010];
ll depth[101010];
ll s[101010], v[101010];
void dfs(ll x){
    visited[x]=1;
    if(x!=1)dp[x] = seg.query(0, v[x])+s[x]+depth[x]*v[x];
    seg.upd(0, {-depth[x], dp[x]}, x);
    for(auto [next,w] : adj[x]){
        if(visited[next])continue;
        depth[next] = depth[x]+w;
        dfs(next);
    }
    if(x!=1){
        seg.rollback(x);
    }
}
int main(){
    fast;
    cin>>n;
    seg.init(-inf1, inf1);
    for(int i = 0 ; i < n-1 ; i++){
        ll a,b,c; cin>>a>>b>>c;
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }
    for(int i = 2 ; i <= n ; i++){
        cin>>s[i]>>v[i];
    }
    dfs(1);
    for(int i = 2 ; i <= n ; i++){
        cout<<dp[i]<<" ";
    }
}

필자는 Line에서 max, min 구현을 잘못해서 하루를 날렸다. 덕분에 애플펜슬도 잃어버리고 공부도 못했다