12736번: Fireworks

https://www.acmicpc.net/problem/12736

i번 연결점에 이어진 폭약들을 시각 t에 동시에 떠뜨리기 위한 최소 비용을 f_i(t)라고 하자. 이 함수는 t에 관한 아래로 볼록인 함수이다.
또한 이 함수는 i번 연결점 바로 다음에 이어진 a0, a1, ..., aj 번 연결점에 관한 최소 비용 함수로부터 구할 수 있다.
(그리 어렵지 않으니 함수가 어떻게 구해지는지 한 번 생각보자.)

이 과정에서 함수끼리의 덧셈 및 볼록껍질의 제약적인 수정이 요구된다.
볼록 함수 끼리의 연산을 효율적으로 하기 위해 볼록 함수를 y절편, 기울기가 1씩 증가하는 t를 우선순위 큐에 저장해놓는다.
- 두 함수를 더하기 위해서는 y절편끼리 더하고 사이즈가 큰 우선순위 큐에 작은 우선순위 큐의 원소들을 모두 빼서 넣어주면 된다. ... (*)
- 볼록 껍질에서 기울기가 1보다 큰 부분을 없애야 하는 경우가 있다. 이 경우엔 간단히 우선순위 큐에서 pop 해주면 된다.
- 볼록 껍질에서 기울기가 -1인 부분을 늘려야 하는 경우가 있다. 이 경우엔 y절편과 기울기가 0인 부분을 잘 수정해주면 된다.

(*) 부분의 시간복잡도를 계산해보자.
먼저, 각 f_i(t)를 이루는 점의 수(곧, 우선순위 큐의 원소 개수)는 i번 연결점에 연결된 폭약의 수에 비례한다. 우선순위 큐 내부의 폭약에 관한 원소들은 (*) 부분에서 이동이 발생하고 그 때마다 자신이 속한 우선순위 큐의 사이즈가 2배이상으로 증가한다. 따라서 각 원소마다 이동횟수가 $O(\lg n)$로 제한되고 이동시 $O(\lg n)$의 시간이 걸리므로 총 시간복잡도는 $O(n\lg^2 n)$.

최종 시간복잡도는 $O(n\lg^2 n)$

#include<cstdio>
#include<queue>
using namespace std;
int n, m, p[300001], c[300001], sz[300001];
long long s[300001], l, r;
priority_queue<long long> *pq[300001];
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 2; i <= n + m; i++) scanf("%d%d", p + i, c + i);
    for (int i = n + 1; i <= n + m; i++) pq[i] = new priority_queue<long long>(2, 0);
    for (int i = n + m; i; i--) {
        while (sz[i]--) pq[i]->pop();
        r = pq[i]->top(); pq[i]->pop();
        l = pq[i]->top(); pq[i]->pop();
        pq[i]->push(l + c[i]);
        pq[i]->push(r + c[i]);
        s[p[i]] += s[i] + c[i];
        if (!pq[p[i]]) { pq[p[i]] = pq[i]; continue; }
        if (pq[p[i]]->size() < pq[i]->size()) swap(pq[p[i]], pq[i]);
        while (!pq[i]->empty()) pq[p[i]]->push(pq[i]->top()), pq[i]->pop();
        sz[p[i]]++;
    }
    pq[0]->pop();
    while (!pq[0]->empty()) s[0] -= pq[0]->top(), pq[0]->pop();
    printf("%lld", s[0]);
    return 0;
}