4256번: 트리

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


$O(tn)$

http://codedoc.tistory.com/779와 유사하다.

#include<cstdio>
int t, n, a[1001], bi[1001];
void f(int al, int ar, int bl, int br) {
    if (al > ar) return;
    int m = bi[a[al]];
    f(al + 1, al + m - bl, bl, m - 1);
    f(al + m - bl + 1, ar, m + 1, br);
    printf("%d ", a[al]);
}
int main() {
    for (scanf("%d", &t); t--;) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d", a + i);
        for (int i = 1, x; i <= n; i++) scanf("%d", &x), bi[x] = i;
        f(1, n, 1, n);
        puts("");
    }
    return 0;
}

4002번: 닌자배치

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


$O(n{lgn}^2)$

i번 닌자를 매니저로 정할 때, i번 닌자의 자손들 중 예산 안에서 월급이 작은 닌자부터 차례대로 고용하는 것이 최선이다.
이 때 고용된 닌자들 집합을 Ai라 하자.
i번 닌자의 자식들을 sj라 하면
언제나 Asj들을 만들 때 제외된 닌자들은 Ai에 존재할 수 없다.(귀류법으로 증명할 수 있다.)
따라서 자식들의 Asj 합집합 + i번 닌자에서 예산이 넘치는 만큼 월급이 큰 닌자부터 제외시킨 집합이 Ai가 된다.
값이 큰 원소부터 제외하는 연산은 우선순위 큐로 구현할 수 있고, 이들을 합칠 때 사이즈가 큰 큐쪽으로 합치면 총 O(nlgn)의 연산횟수에 문제를 해결할 수 있다.

#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int MXN = 1e5;
int n, m, p[MXN + 1];
ll c[MXN + 1], l[MXN + 1], r;
priority_queue<int> pq[MXN + 1];
vector<int> adj[MXN + 1];
void f(int h) {
    p[h] = h;
    pq[h].push(c[h]);
    for (auto it : adj[h]) {
        f(it);
        if (pq[p[h]].size() < pq[p[it]].size()) swap(p[h], p[it]);
        while (!pq[p[it]].empty()) pq[p[h]].push(pq[p[it]].top()), pq[p[it]].pop();
        c[h] += c[it];
    }
    while (c[h] > m) c[h] -= pq[p[h]].top(), pq[p[h]].pop();
    r = max(r, (ll)pq[p[h]].size()*l[h]);
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1, x; i <= n; i++) {
        scanf("%d%lld%lld", &x, c + i, l + i);
        adj[x].push_back(i);
    }
    f(1);
    printf("%lld", r);
    return 0;
}

$O(nlgn)$

처음 아이디어는 위와 같다.
트리를 순회하면서 번호를 매기면 어떤 정점의 자손들이 모두 인접한 번호를 가지고 있게 할 수 있다.
세그먼트 트리를 이용해 해당 구역에서 월급이 가장 큰 닌자를 O(lgn)에 찾고 제거할 수 있다.

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MXN = 1e5;
int n, m, l[MXN + 1], p[MXN + 1], cnt;
ll c[MXN + 1], r;
pair<int, int> tree[MXN * 4];
vector<int> adj[MXN + 1];
void insert(int h, int s, int e, int g, int x) {
    if (e < g || g < s) return;
    if (s == e) {
        tree[h] = { x,g };
        return;
    }
    insert(h * 2 + 1, s, (s + e) / 2, g, x);
    insert(h * 2 + 2, (s + e) / 2 + 1, e, g, x);
    tree[h] = max(tree[h * 2 + 1], tree[h * 2 + 2]);
}
pair<int, int> find(int h, int s, int e, int gs, int ge) {
    if (ge < s || e < gs) return{ 0,0 };
    if (gs <= s&&e <= ge) return tree[h];
    return max(find(h * 2 + 1, s, (s + e) / 2, gs, ge), find(h * 2 + 2, (s + e) / 2 + 1, e, gs, ge));
}
void f(int h) {
    int s = cnt;
    p[h]++;
    insert(0, 0, n - 1, cnt++, c[h]);
    for (auto it : adj[h]) {
        f(it);
        c[h] += c[it];
        p[h] += p[it];
    }
    while (c[h] > m) {
        pair<int, int> t = find(0, 0, n - 1, s, cnt - 1);
        insert(0, 0, n - 1, t.second, 0);
        c[h] -= t.first;
        p[h]--;
    }
    r = max(r, (ll)p[h] * l[h]);
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1, x; i <= n; i++) {
        scanf("%d%lld%d", &x, c + i, l + i);
        adj[x].push_back(i);
    }
    f(1);
    printf("%lld", r);
    return 0;
}

2263번: 트리의 순회

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


$O(n)$

인오더 수열 ai
포스트오더 수열 bi

f(al,ar,bl,br): ai는 [l,r], bi는 [l,r]을 보고 있다고 하자.
br은 현재보고 있는 수열 중 루트임을 알 수 있다.
또한 br과 같은 ax 좌, 우에 있는 항들로 서브트리가 갈라짐을 알 수 있다.
여기서 좌, 우 서브트리의 자식 노드 개수를 알 수 있고 이를 이용해 bi의 항들을 나눠 f를 호출한다.

#include<cstdio>
const int MXN = 1e5;
int n, b[MXN], ai[MXN + 1];
void f(int al, int ar, int bl, int br) {
    if (bl > br) return;
    printf("%d ", b[br]);
    f(al, ai[b[br]] - 1, bl, ai[b[br]] - 1 - al + bl);
    f(ai[b[br]] + 1, ar, br - ar + ai[b[br]], br - 1);
}
int main() {
    scanf("%d", &n);
    for (int i = 0, x; i < n; i++) scanf("%d", &x), ai[x] = i;
    for (int i = 0; i < n; i++) scanf("%d", b + i);
    f(0, n - 1, 0, n - 1);
    return 0;
}

1991번: 트리 순회

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


$O(n)$

#include<cstdio>
int n, l[99], r[99];
char x, y, z;
void f(int h, int c) {
    if (h == '.') return;
    if (!c) putchar(h);
    f(l[h], c);
    if (c == 1) putchar(h);
    f(r[h], c);
    if (c == 2) putchar(h);
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf(" %c %c %c", &x, &y, &z);
        l[x] = y; r[x] = z;
    }
    for (int i = 0; i < 3; i++) f('A', i), puts("");
    return 0;
}

2820번: 자동차 공장

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


$O((n+m)\lg n)$

노란 책에도 비슷한게 있는 유명한 문제

#include<stdio.h>
#include<vector>
using namespace std;
const int MAX_N = 5e5;
int n, m, d[MAX_N + 1], u[MAX_N + 1], cnt, w[MAX_N + 1], s[MAX_N + 1];
vector<int> adj[MAX_N + 1];
void dfs(int h) {
    d[h] = ++cnt;
    for (auto it : adj[h]) dfs(it);
    u[h] = cnt;
}
void update(int h, int x) { for (; h <= n; h += h&-h) s[h] += x; }
int query(int h) {
    int r = 0;
    for (; h; h -= h&-h) r += s[h];
    return r;
}
int main() {
    scanf("%d %d %d", &n, &m, w + 1);
    for (int i = 2, p; i <= n; i++) scanf("%d %d", w + i, &p), adj[p].push_back(i);
    dfs(1);
    for (int i = 1; i <= n; i++) update(d[i], w[i]), update(d[i] + 1, -w[i]);
    for (int i = 0, a, b; i < m; i++) {
        char c;
        scanf(" %c", &c);
        if (c == 'p') {
            scanf("%d %d", &a, &b);
            update(d[a] + 1, b);
            update(u[a] + 1, -b);
        }
        else {
            scanf("%d", &a);
            printf("%d\n", query(d[a]));
        }
    }
    return 0;
}