26.6 แบบฝึกหัด

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> parent(n + 1), child_count(n + 1, 0);
    for (int v = 1; v <= n; v++) {
        cin >> parent[v];
        if (parent[v] != 0) {
            child_count[parent[v]]++;
        }
    }
    int leaves = 0, height = 0;
    for (int v = 1; v <= n; v++) {
        if (child_count[v] == 0) {
            leaves++;
        }
        int depth = 0;
        for (int u = v; parent[u] != 0; u = parent[u]) {
            depth++;
        }
        height = max(height, depth);
    }
    cout << leaves << '\n' << height << '\n';
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

vector<int> left_child, right_child, visited;

void preorder(int v)
{
    if (v == 0) {
        return;
    }
    visited.push_back(v);
    preorder(left_child[v]);
    preorder(right_child[v]);
}

void inorder(int v)
{
    if (v == 0) {
        return;
    }
    inorder(left_child[v]);
    visited.push_back(v);
    inorder(right_child[v]);
}

void postorder(int v)
{
    if (v == 0) {
        return;
    }
    postorder(left_child[v]);
    postorder(right_child[v]);
    visited.push_back(v);
}

void print_and_clear()
{
    for (int i = 0; i < (int)visited.size(); i++) {
        if (i > 0) {
            cout << ' ';
        }
        cout << visited[i];
    }
    cout << '\n';
    visited.clear();
}

int main()
{
    int n;
    cin >> n;
    left_child.assign(n + 1, 0);
    right_child.assign(n + 1, 0);
    vector<bool> has_parent(n + 1, false);
    for (int v = 1; v <= n; v++) {
        cin >> left_child[v] >> right_child[v];
        has_parent[left_child[v]] = true;
        has_parent[right_child[v]] = true;
    }
    int root = 0;
    for (int v = 1; v <= n; v++) {
        if (!has_parent[v]) {
            root = v;
        }
    }
    preorder(root);
    print_and_clear();
    inorder(root);
    print_and_clear();
    postorder(root);
    print_and_clear();
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<vector<int>> children(n + 1);
    int root = 0;
    for (int v = 1; v <= n; v++) {
        int p;
        cin >> p;
        if (p == 0) {
            root = v;
        } else {
            children[p].push_back(v);
        }
    }
    vector<int> depth(n + 1, 0), count_at;
    queue<int> waiting;
    waiting.push(root);
    while (!waiting.empty()) {
        int v = waiting.front();
        waiting.pop();
        if (depth[v] == (int)count_at.size()) {
            count_at.push_back(0);
        }
        count_at[depth[v]]++;
        for (int c : children[v]) {
            depth[c] = depth[v] + 1;
            waiting.push(c);
        }
    }
    for (int k = 0; k < (int)count_at.size(); k++) {
        if (k > 0) {
            cout << ' ';
        }
        cout << count_at[k];
    }
    cout << '\n';
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> boss(n + 1);
    vector<vector<int>> team(n + 1);
    int root = 0;
    for (int v = 1; v <= n; v++) {
        cin >> boss[v];
        if (boss[v] == 0) {
            root = v;
        } else {
            team[boss[v]].push_back(v);
        }
    }
    vector<long long> total(n + 1);
    for (int v = 1; v <= n; v++) {
        cin >> total[v];
    }
    vector<int> order;
    stack<int> waiting;
    waiting.push(root);
    while (!waiting.empty()) {
        int v = waiting.top();
        waiting.pop();
        order.push_back(v);
        for (int c : team[v]) {
            waiting.push(c);
        }
    }
    for (int i = n - 1; i >= 1; i--) {
        int v = order[i];
        total[boss[v]] += total[v];
    }
    for (int v = 1; v <= n; v++) {
        if (v > 1) {
            cout << ' ';
        }
        cout << total[v];
    }
    cout << '\n';
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> parent(n + 1);
    vector<vector<int>> children(n + 1);
    int root = 0;
    for (int v = 1; v <= n; v++) {
        cin >> parent[v];
        if (parent[v] == 0) {
            root = v;
        } else {
            children[parent[v]].push_back(v);
        }
    }
    vector<int> height(n + 1);
    for (int v = 1; v <= n; v++) {
        cin >> height[v];
    }
    vector<int> best(n + 1, 0);
    int peaks = 0;
    stack<int> waiting;
    waiting.push(root);
    while (!waiting.empty()) {
        int v = waiting.top();
        waiting.pop();
        int before = (v == root) ? 0 : best[parent[v]];
        if (height[v] > before) {
            peaks++;
        }
        best[v] = max(before, height[v]);
        for (int c : children[v]) {
            waiting.push(c);
        }
    }
    cout << peaks << '\n';
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

vector<int> heap = {0};

void sift_up(int i)
{
    while (i > 1 && heap[i / 2] < heap[i]) {
        swap(heap[i / 2], heap[i]);
        i /= 2;
    }
}

void sift_down(int i)
{
    int n = (int)heap.size() - 1;
    while (2 * i <= n) {
        int child = 2 * i;
        if (child + 1 <= n && heap[child + 1] > heap[child]) {
            child++;
        }
        if (heap[i] >= heap[child]) {
            break;
        }
        swap(heap[i], heap[child]);
        i = child;
    }
}

void print_heap()
{
    if (heap.size() == 1) {
        cout << "empty\n";
        return;
    }
    for (int i = 1; i < (int)heap.size(); i++) {
        if (i > 1) {
            cout << ' ';
        }
        cout << heap[i];
    }
    cout << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    heap.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> heap[i];
    }
    for (int i = n / 2; i >= 1; i--) {
        sift_down(i);
    }
    print_heap();
    int q;
    cin >> q;
    for (int k = 0; k < q; k++) {
        char op;
        cin >> op;
        if (op == '+') {
            int x;
            cin >> x;
            heap.push_back(x);
            sift_up((int)heap.size() - 1);
        } else {
            cout << heap[1] << '\n';
            heap[1] = heap.back();
            heap.pop_back();
            if (heap.size() > 1) {
                sift_down(1);
            }
        }
    }
    print_heap();
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int key;
    Node *left;
    Node *right;
};

Node *insert(Node *root, int key)
{
    Node *node = new Node;
    node->key = key;
    node->left = nullptr;
    node->right = nullptr;
    if (root == nullptr) {
        return node;
    }
    Node *cur = root;
    while (true) {
        if (key < cur->key) {
            if (cur->left == nullptr) {
                cur->left = node;
                break;
            }
            cur = cur->left;
        } else {
            if (cur->right == nullptr) {
                cur->right = node;
                break;
            }
            cur = cur->right;
        }
    }
    return root;
}

Node *erase(Node *node, int key)
{
    if (node == nullptr) {
        return nullptr;
    }
    if (key < node->key) {
        node->left = erase(node->left, key);
        return node;
    }
    if (key > node->key) {
        node->right = erase(node->right, key);
        return node;
    }
    if (node->left == nullptr) {
        Node *child = node->right;
        delete node;
        return child;
    }
    if (node->right == nullptr) {
        Node *child = node->left;
        delete node;
        return child;
    }
    Node *next = node->right;
    while (next->left != nullptr) {
        next = next->left;
    }
    node->key = next->key;
    node->right = erase(node->right, next->key);
    return node;
}

int depth_of(Node *root, int key)
{
    int depth = 0;
    Node *cur = root;
    while (cur != nullptr) {
        if (key == cur->key) {
            return depth;
        }
        if (key < cur->key) {
            cur = cur->left;
        } else {
            cur = cur->right;
        }
        depth++;
    }
    return -1;
}

void preorder(Node *node, vector<int> &keys)
{
    if (node == nullptr) {
        return;
    }
    keys.push_back(node->key);
    preorder(node->left, keys);
    preorder(node->right, keys);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> q;
    Node *root = nullptr;
    for (int k = 0; k < q; k++) {
        char op;
        int x;
        cin >> op >> x;
        if (op == '+') {
            root = insert(root, x);
        } else if (op == '-') {
            root = erase(root, x);
        } else {
            cout << depth_of(root, x) << '\n';
        }
    }
    vector<int> keys;
    preorder(root, keys);
    if (keys.empty()) {
        cout << "empty";
    }
    for (int i = 0; i < (int)keys.size(); i++) {
        if (i > 0) {
            cout << ' ';
        }
        cout << keys[i];
    }
    cout << '\n';
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> parent(n + 1);
    vector<vector<int>> children(n + 1);
    int root = 0;
    for (int v = 1; v <= n; v++) {
        cin >> parent[v];
        if (parent[v] == 0) {
            root = v;
        } else {
            children[parent[v]].push_back(v);
        }
    }
    vector<long long> length(n + 1);
    for (int v = 1; v <= n; v++) {
        cin >> length[v];
    }
    vector<int> order;
    stack<int> waiting;
    waiting.push(root);
    while (!waiting.empty()) {
        int v = waiting.top();
        waiting.pop();
        order.push_back(v);
        for (int c : children[v]) {
            waiting.push(c);
        }
    }
    vector<long long> longest(n + 1, 0), second(n + 1, 0);
    long long answer = 0;
    for (int i = n - 1; i >= 0; i--) {
        int v = order[i];
        answer = max(answer, longest[v] + second[v]);
        int p = parent[v];
        if (p == 0) {
            continue;
        }
        long long down = longest[v] + length[v];
        if (down > longest[p]) {
            second[p] = longest[p];
            longest[p] = down;
        } else if (down > second[p]) {
            second[p] = down;
        }
    }
    cout << answer << '\n';
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    set<int> inserted;
    map<int, int> depth;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        int d = 0;
        auto after = inserted.lower_bound(x);
        if (after != inserted.end()) {
            d = max(d, depth[*after] + 1);
        }
        if (after != inserted.begin()) {
            d = max(d, depth[*prev(after)] + 1);
        }
        inserted.insert(x);
        depth[x] = d;
        if (i > 0) {
            cout << ' ';
        }
        cout << d;
    }
    cout << '\n';
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> boss(n + 1);
    vector<vector<int>> team(n + 1);
    int root = 0;
    for (int v = 1; v <= n; v++) {
        cin >> boss[v];
        if (boss[v] == 0) {
            root = v;
        } else {
            team[boss[v]].push_back(v);
        }
    }
    vector<long long> take(n + 1), skip(n + 1, 0);
    for (int v = 1; v <= n; v++) {
        cin >> take[v];
    }
    vector<int> order;
    stack<int> waiting;
    waiting.push(root);
    while (!waiting.empty()) {
        int v = waiting.top();
        waiting.pop();
        order.push_back(v);
        for (int c : team[v]) {
            waiting.push(c);
        }
    }
    for (int i = n - 1; i >= 1; i--) {
        int v = order[i];
        take[boss[v]] += skip[v];
        skip[boss[v]] += max(take[v], skip[v]);
    }
    cout << max(take[root], skip[root]) << '\n';
    return 0;
}