verify/yosupo-rooted-tree-topological-order-with-minimum-inversions.test.cpp

• View this file on GitHub
• Last update: 2026-05-31 17:59:37+09:00
• Problem: https://judge.yosupo.jp/problem/rooted_tree_topological_order_with_minimum_inversions

Depends on

• 01 on Tree (graph/tree/01-on-tree.hpp)

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/rooted_tree_topological_order_with_minimum_inversions

#include <iostream>
#include <queue>
#include <utility>
#include <vector>

#include "../graph/tree/01-on-tree.hpp"

std::vector<int>
build_01_on_tree_order(int n, const std::vector<std::pair<int, int>> &edges,
                       const std::vector<long long> &c0,
                       const std::vector<long long> &c1, int root) {
    std::vector<std::vector<int>> graph(n);
    for (const auto &[from, to] : edges) {
        graph[from].push_back(to);
        graph[to].push_back(from);
    }

    std::vector<int> parent(n, -2);
    parent[root] = -1;
    std::vector<int> stack{root};
    while (!stack.empty()) {
        const int v = stack.back();
        stack.pop_back();
        for (int to : graph[v]) {
            if (to == parent[v]) {
                continue;
            }
            if (parent[to] != -2) {
                continue;
            }
            parent[to] = v;
            stack.push_back(to);
        }
    }

    struct QueueNode {
        int vertex;
        int version;
        long long zero;
        long long one;
    };

    struct QueueCompare {
        bool operator()(const QueueNode &a, const QueueNode &b) const {
            if (a.one == 0 && b.one == 0) {
                return a.vertex < b.vertex;
            }
            if (a.one == 0) {
                return false;
            }
            if (b.one == 0) {
                return true;
            }
            const long long lhs = a.zero * b.one;
            const long long rhs = b.zero * a.one;
            if (lhs < rhs) {
                return true;
            }
            if (rhs < lhs) {
                return false;
            }
            return a.vertex < b.vertex;
        }
    };

    std::vector<int> leader(n), up = parent, version(n, 0), head(n), tail(n),
                                next(n, -1);
    std::vector<long long> zero = c0, one = c1;
    for (int v = 0; v < n; ++v) {
        leader[v] = v;
        head[v] = v;
        tail[v] = v;
    }

    auto find = [&](int v) {
        while (leader[v] != v) {
            leader[v] = leader[leader[v]];
            v = leader[v];
        }
        return v;
    };

    std::priority_queue<QueueNode, std::vector<QueueNode>, QueueCompare> que;
    auto push = [&](int v) {
        if (up[v] != -1) {
            que.push(QueueNode{v, version[v], zero[v], one[v]});
        }
    };

    for (int v = 0; v < n; ++v) {
        push(v);
    }

    for (int merge_count = 0; merge_count < n - 1; ++merge_count) {
        QueueNode current{};
        while (true) {
            current = que.top();
            que.pop();
            const int v = find(current.vertex);
            if (v == current.vertex && current.version == version[v]) {
                break;
            }
        }

        const int v = current.vertex;
        const int p = find(up[v]);
        next[tail[p]] = head[v];
        tail[p] = tail[v];
        zero[p] += zero[v];
        one[p] += one[v];
        leader[v] = p;
        ++version[p];
        push(p);
    }

    std::vector<int> order;
    order.reserve(n);
    for (int v = head[root]; v != -1; v = next[v]) {
        order.push_back(v);
    }
    return order;
}

int main() {
    int n;
    std::cin >> n;

    const int root = n;
    std::vector<std::pair<int, int>> edges;
    edges.reserve(n);
    for (int i = 1; i < n; ++i) {
        int p;
        std::cin >> p;
        edges.push_back({p, i});
    }
    edges.push_back({root, 0});

    std::vector<long long> c0(n + 1, 0), c1(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        std::cin >> c0[i];
    }
    for (int i = 0; i < n; ++i) {
        std::cin >> c1[i];
    }

    const long long answer =
        solve_01_on_tree<long long>(n + 1, edges, c0, c1, root);
    const std::vector<int> order =
        build_01_on_tree_order(n + 1, edges, c0, c1, root);

    std::cout << answer << '\n';
    bool first = true;
    for (int v : order) {
        if (v == root) {
            continue;
        }
        if (!first) {
            std::cout << ' ';
        }
        first = false;
        std::cout << v;
    }
    std::cout << '\n';
    return 0;
}

#line 1 "verify/yosupo-rooted-tree-topological-order-with-minimum-inversions.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/rooted_tree_topological_order_with_minimum_inversions

#include <iostream>
#include <queue>
#include <utility>
#include <vector>

#line 1 "graph/tree/01-on-tree.hpp"



// 根付き木上で、親が子より左に出る順序の 01 列の転倒数最小値を求める。
// 頂点 v には c0[v] 個の 0 の後に c1[v] 個の 1 を置いた列が書かれている。
// 辺は無向辺の両端で与え、root を根として親子関係を定める。
// c0[v], c1[v] は非負の個数である。計算量は O(n log n) である。

#include <cassert>
#line 11 "graph/tree/01-on-tree.hpp"
#include <type_traits>
#line 14 "graph/tree/01-on-tree.hpp"

namespace zero_one_on_tree_impl {
template <class InputCount, class Preferred>
using count_type_t = std::conditional_t<
    !std::is_class_v<Preferred> && !std::is_floating_point_v<Preferred> &&
        (sizeof(InputCount) < sizeof(Preferred)),
    Preferred,
    std::conditional_t<(sizeof(InputCount) < sizeof(long long)),
                       std::conditional_t<std::is_signed_v<InputCount>,
                                          long long, unsigned long long>,
                       InputCount>>;

template <class Count>
int compare_fraction(Count a_num, Count a_den, Count b_num, Count b_den) {
    bool reversed = false;
    while (true) {
        const Count a_quot = a_num / a_den;
        const Count b_quot = b_num / b_den;
        if (a_quot != b_quot) {
            const int result = a_quot < b_quot ? -1 : 1;
            return reversed ? -result : result;
        }

        a_num %= a_den;
        b_num %= b_den;
        if (a_num == Count{} || b_num == Count{}) {
            int result = 0;
            if (a_num != b_num) {
                result = a_num == Count{} ? -1 : 1;
            }
            return reversed ? -result : result;
        }

        std::swap(a_num, a_den);
        std::swap(b_num, b_den);
        reversed = !reversed;
    }
}
} // namespace zero_one_on_tree_impl

template <class T = void, class InputCount>
std::conditional_t<std::is_void_v<T>,
                   zero_one_on_tree_impl::count_type_t<InputCount, InputCount>,
                   T>
solve_01_on_tree(int n, const std::vector<std::pair<int, int>> &edges,
                 const std::vector<InputCount> &c0,
                 const std::vector<InputCount> &c1, int root = 0) {
    using Preferred = std::conditional_t<std::is_void_v<T>, InputCount, T>;
    using Count = zero_one_on_tree_impl::count_type_t<InputCount, Preferred>;
    using Answer = std::conditional_t<std::is_void_v<T>, Count, T>;

    assert(n >= 1);
    assert(static_cast<int>(edges.size()) == n - 1);
    assert(static_cast<int>(c0.size()) == n);
    assert(static_cast<int>(c1.size()) == n);
    assert(0 <= root && root < n);

    std::vector<std::vector<int>> graph(n);
    std::vector<Count> zero(n), one(n);
    for (int v = 0; v < n; ++v) {
        assert(!(c0[v] < InputCount{}));
        assert(!(c1[v] < InputCount{}));
        zero[v] = static_cast<Count>(c0[v]);
        one[v] = static_cast<Count>(c1[v]);
    }
    for (const auto &[from, to] : edges) {
        assert(0 <= from && from < n);
        assert(0 <= to && to < n);
        assert(from != to);
        graph[from].push_back(to);
        graph[to].push_back(from);
    }

    std::vector<int> parent(n, -2);
    parent[root] = -1;
    int visited = 0;
    std::vector<int> stack{root};
    while (!stack.empty()) {
        const int v = stack.back();
        stack.pop_back();
        ++visited;
        for (int to : graph[v]) {
            if (to == parent[v]) {
                continue;
            }
            assert(parent[to] == -2);
            parent[to] = v;
            stack.push_back(to);
        }
    }
    assert(visited == n);

    struct QueueNode {
        int vertex;
        int version;
        Count zero;
        Count one;
    };

    struct QueueCompare {
        bool operator()(const QueueNode &a, const QueueNode &b) const {
            if (a.one == Count{} && b.one == Count{}) {
                return a.vertex < b.vertex;
            }
            if (a.one == Count{}) {
                return false;
            }
            if (b.one == Count{}) {
                return true;
            }
            const int result = zero_one_on_tree_impl::compare_fraction(
                a.zero, a.one, b.zero, b.one);
            if (result < 0) {
                return true;
            }
            if (result > 0) {
                return false;
            }
            return a.vertex < b.vertex;
        }
    };

    std::vector<int> leader(n), up = parent, version(n, 0);
    for (int v = 0; v < n; ++v) {
        leader[v] = v;
    }

    auto find = [&](int v) {
        while (leader[v] != v) {
            leader[v] = leader[leader[v]];
            v = leader[v];
        }
        return v;
    };

    std::priority_queue<QueueNode, std::vector<QueueNode>, QueueCompare> que;
    auto push = [&](int v) {
        if (up[v] != -1) {
            que.push(QueueNode{v, version[v], zero[v], one[v]});
        }
    };

    for (int v = 0; v < n; ++v) {
        push(v);
    }

    Answer answer{};
    for (int merge_count = 0; merge_count < n - 1; ++merge_count) {
        QueueNode current{};
        while (true) {
            assert(!que.empty());
            current = que.top();
            que.pop();
            const int v = find(current.vertex);
            if (v == current.vertex && current.version == version[v]) {
                break;
            }
        }

        const int v = current.vertex;
        const int p = find(up[v]);
        assert(p != v);

        answer += static_cast<Answer>(one[p]) * static_cast<Answer>(zero[v]);
        zero[p] += zero[v];
        one[p] += one[v];
        leader[v] = p;
        ++version[p];
        push(p);
    }

    return answer;
}


#line 9 "verify/yosupo-rooted-tree-topological-order-with-minimum-inversions.test.cpp"

std::vector<int>
build_01_on_tree_order(int n, const std::vector<std::pair<int, int>> &edges,
                       const std::vector<long long> &c0,
                       const std::vector<long long> &c1, int root) {
    std::vector<std::vector<int>> graph(n);
    for (const auto &[from, to] : edges) {
        graph[from].push_back(to);
        graph[to].push_back(from);
    }

    std::vector<int> parent(n, -2);
    parent[root] = -1;
    std::vector<int> stack{root};
    while (!stack.empty()) {
        const int v = stack.back();
        stack.pop_back();
        for (int to : graph[v]) {
            if (to == parent[v]) {
                continue;
            }
            if (parent[to] != -2) {
                continue;
            }
            parent[to] = v;
            stack.push_back(to);
        }
    }

    struct QueueNode {
        int vertex;
        int version;
        long long zero;
        long long one;
    };

    struct QueueCompare {
        bool operator()(const QueueNode &a, const QueueNode &b) const {
            if (a.one == 0 && b.one == 0) {
                return a.vertex < b.vertex;
            }
            if (a.one == 0) {
                return false;
            }
            if (b.one == 0) {
                return true;
            }
            const long long lhs = a.zero * b.one;
            const long long rhs = b.zero * a.one;
            if (lhs < rhs) {
                return true;
            }
            if (rhs < lhs) {
                return false;
            }
            return a.vertex < b.vertex;
        }
    };

    std::vector<int> leader(n), up = parent, version(n, 0), head(n), tail(n),
                                next(n, -1);
    std::vector<long long> zero = c0, one = c1;
    for (int v = 0; v < n; ++v) {
        leader[v] = v;
        head[v] = v;
        tail[v] = v;
    }

    auto find = [&](int v) {
        while (leader[v] != v) {
            leader[v] = leader[leader[v]];
            v = leader[v];
        }
        return v;
    };

    std::priority_queue<QueueNode, std::vector<QueueNode>, QueueCompare> que;
    auto push = [&](int v) {
        if (up[v] != -1) {
            que.push(QueueNode{v, version[v], zero[v], one[v]});
        }
    };

    for (int v = 0; v < n; ++v) {
        push(v);
    }

    for (int merge_count = 0; merge_count < n - 1; ++merge_count) {
        QueueNode current{};
        while (true) {
            current = que.top();
            que.pop();
            const int v = find(current.vertex);
            if (v == current.vertex && current.version == version[v]) {
                break;
            }
        }

        const int v = current.vertex;
        const int p = find(up[v]);
        next[tail[p]] = head[v];
        tail[p] = tail[v];
        zero[p] += zero[v];
        one[p] += one[v];
        leader[v] = p;
        ++version[p];
        push(p);
    }

    std::vector<int> order;
    order.reserve(n);
    for (int v = head[root]; v != -1; v = next[v]) {
        order.push_back(v);
    }
    return order;
}

int main() {
    int n;
    std::cin >> n;

    const int root = n;
    std::vector<std::pair<int, int>> edges;
    edges.reserve(n);
    for (int i = 1; i < n; ++i) {
        int p;
        std::cin >> p;
        edges.push_back({p, i});
    }
    edges.push_back({root, 0});

    std::vector<long long> c0(n + 1, 0), c1(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        std::cin >> c0[i];
    }
    for (int i = 0; i < n; ++i) {
        std::cin >> c1[i];
    }

    const long long answer =
        solve_01_on_tree<long long>(n + 1, edges, c0, c1, root);
    const std::vector<int> order =
        build_01_on_tree_order(n + 1, edges, c0, c1, root);

    std::cout << answer << '\n';
    bool first = true;
    for (int v : order) {
        if (v == root) {
            continue;
        }
        if (!first) {
            std::cout << ' ';
        }
        first = false;
        std::cout << v;
    }
    std::cout << '\n';
    return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	almost_line_00	AC	1656 ms	39 MB
g++	almost_line_01	AC	1653 ms	39 MB
g++	example_00	AC	2 ms	4 MB
g++	example_01	AC	2 ms	4 MB
g++	max_bival_00	AC	1200 ms	39 MB
g++	max_bival_01	AC	1194 ms	39 MB
g++	max_bival_02	AC	1209 ms	39 MB
g++	max_random_00	AC	1513 ms	39 MB
g++	max_random_01	AC	1484 ms	39 MB
g++	max_random_02	AC	1522 ms	40 MB
g++	max_random_03	AC	1560 ms	40 MB
g++	max_random_04	AC	1556 ms	39 MB
g++	max_typical_tree_00	AC	1752 ms	38 MB
g++	max_typical_tree_01	AC	920 ms	40 MB
g++	max_typical_tree_02	AC	912 ms	41 MB
g++	max_typical_tree_03	AC	1423 ms	39 MB
g++	min_00	AC	2 ms	4 MB
g++	min_01	AC	2 ms	3 MB
g++	min_02	AC	2 ms	4 MB
g++	random_00	AC	884 ms	25 MB
g++	random_01	AC	1104 ms	32 MB
g++	random_02	AC	324 ms	13 MB
g++	random_03	AC	1230 ms	35 MB
g++	random_04	AC	79 ms	6 MB
g++	two_path_00	AC	1883 ms	38 MB
g++	two_path_01	AC	769 ms	40 MB
g++	two_path_02	AC	1549 ms	38 MB
g++	two_path_03	AC	1557 ms	39 MB
g++	two_path_04	AC	806 ms	39 MB
g++	weight_zero_00	AC	1301 ms	39 MB
clang++	almost_line_00	AC	1494 ms	38 MB
clang++	almost_line_01	AC	1473 ms	38 MB
clang++	example_00	AC	2 ms	3 MB
clang++	example_01	AC	2 ms	4 MB
clang++	max_bival_00	AC	1056 ms	40 MB
clang++	max_bival_01	AC	1055 ms	39 MB
clang++	max_bival_02	AC	1057 ms	39 MB
clang++	max_random_00	AC	1353 ms	39 MB
clang++	max_random_01	AC	1378 ms	40 MB
clang++	max_random_02	AC	1359 ms	40 MB
clang++	max_random_03	AC	1369 ms	39 MB
clang++	max_random_04	AC	1342 ms	39 MB
clang++	max_typical_tree_00	AC	1592 ms	39 MB
clang++	max_typical_tree_01	AC	827 ms	42 MB
clang++	max_typical_tree_02	AC	848 ms	40 MB
clang++	max_typical_tree_03	AC	1271 ms	39 MB
clang++	min_00	AC	2 ms	4 MB
clang++	min_01	AC	2 ms	3 MB
clang++	min_02	AC	2 ms	4 MB
clang++	random_00	AC	784 ms	25 MB
clang++	random_01	AC	961 ms	33 MB
clang++	random_02	AC	284 ms	13 MB
clang++	random_03	AC	1092 ms	34 MB
clang++	random_04	AC	70 ms	6 MB
clang++	two_path_00	AC	1569 ms	40 MB
clang++	two_path_01	AC	647 ms	38 MB
clang++	two_path_02	AC	1369 ms	38 MB
clang++	two_path_03	AC	1302 ms	38 MB
clang++	two_path_04	AC	681 ms	39 MB
clang++	weight_zero_00	AC	1170 ms	40 MB

Back to top page