백준 3319번 전령들

문제 요약

크기 N인 트리가 주어지고 각 노드에는 1부터 N까지 번호가 붙어있다.

각 노드는 도시라고 볼 수 있는데 각 도시에는 전령이 있다. 각 도시에 살고 있는 전령들이 1번 도시로 메시지를 전달하고자 한다.

각 도시의 전령이 출발하는데 준비하는 시간과 거리 1을 가는 데에 걸리는 시간인 $S_i, V_i$가 주어진다.

각 도시에 도착할 때마다 그 도시에 있는 전령으로 갈아타거나 이전에 이용하던 전령을 그대로 이용할지를 선택할 수 있다.

이 때, 각 도시에서 1번 도시로 메시지를 보내는 데에 걸리는 최소시간을 구해야 한다.

풀이

별로 쓸모 있는 말은 아니지만 정말 멋진 문제라고 생각한다.

일단 i번 도시에서 1번 도시까지의 최소 거리를 dp(i)라고 하자. 그러면 아래와 같이 정의할 수 있다.
$$
\begin{aligned}
dp(i) &= \underset{p \in ancestors(i)}{min}((dist(i)-dist(p))V_i + S_i +dp(p)) \\
dp(i) &= \underset{p \in ancestors(i)}{min}(-dist(p)V_i + dp(p)) +dist(i)V_i+S_i
\end{aligned}
$$
여기서 $dist(i)$는 1번노드부터 i번 노드까지의 거리를 뜻한다. Convex Hull Trick을 사용할 수 있는 꼴이 됐다.

1번부터 DFS를 진행하면서 i번에 도착했을 때 생기는 Convex Hull에 대해서 쿼리를 날려야 한다.

DFS를 진행하면서 Convex Hull에 직선을 추가하게 되는데 스택의 제일 끝부터 보면서 있는 직선을 삭제하게 되면 DFS를 더 진행할 곳이 없어서 돌아오고 새롭게 DFS를 진행하려고 할 때 이전 직선의 정보들이 날라가는 문제가 발생한다.

먼저 DFS를 진행하면서 추가되는 직선들의 기울기는 단조 감소하게 된다. 따라서, 항상 Convex Hull에 추가되는 것은 보장이 된다.

그리고 이 직선이 스택의 어느 위치에 추가될지는 이분탐색으로 찾을 수 있다. 이렇게 찾은 위치에 직선을 넣어주고 DFS를 진행하도록 한다.

이 때, 추가했던 위치와 그 위치에 있던 직선을 들고 있는다. 그러면 해당 노드에 대한 DFS가 종료될 때 이를 돌려놓음으로 원래의 Convex Hull을 보존할 수 있다.

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

struct Line{
    ll m, b;
    Line() : m(0), b(0) {};
    Line(ll m_, ll b_) : m(m_), b(b_) {};
    ll f(ll x) { return m*x + b; }
};

vector<Line> lines;
int ptr = 1;
vector<ll> dp, V, S;
vector<vector<pair<int,ll>>> G;
int N;

ld intersect(Line &a, Line &b) {
    return (ld)(a.b - b.b)/(b.m - a.m);
}

int add_line(Line &line) {
    int lo = 1, hi = ptr;
    while(lo < hi) {
        int mid = lo + hi >> 1;
        if(intersect(lines[mid-1], line) < intersect(lines[mid], lines[mid-1])) hi = mid;
        else lo = mid+1;
    }
    return lo;
}

ll query(ll x) {
    int lo = 0, hi = ptr - 1;
    while(lo < hi) {
        int mid = (lo + hi + 1) >> 1;
        if(intersect(lines[mid], lines[mid-1]) < x) lo = mid;
        else hi = mid-1;
    }
    return lines[lo].f(x);
}

void dfs(int cur, int par, ll dist) {
    int rb_idx, rb_ptr = ptr;
    Line rb_line;
    if(par) {
        dp[cur] = query(V[cur]) + dist * V[cur] + S[cur];
        Line cur_line(-dist, dp[cur]);
        rb_idx = add_line(cur_line);
        rb_line = lines[rb_idx];
        lines[rb_idx] = cur_line;
        ptr = rb_idx+1;
    }
    for(auto &nxt:G[cur]) {
        int v = nxt.first;
        ll w = nxt.second;
        if(v == par) continue;
        dfs(v, cur, dist+w);
    }
    if(par) {
        lines[rb_idx] = rb_line;
        ptr = rb_ptr;
    }
}

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> N;
    dp.resize(N+1); S.resize(N+1); V.resize(N+1);
    G.resize(N+1); lines.resize(N+1, Line());
    for(int i=1;i<N;++i) {
        int u, v, w;
        cin >> u >> v >> w;
        G[u].emplace_back(v,w);
        G[v].emplace_back(u,w);
    }
    for(int i=2;i<=N;++i) cin >> S[i] >> V[i];
    dfs(1, 0, 0);
    for(int i=2;i<=N;++i) cout << dp[i] << " \n"[i==N];
    return 0;
}