#1195925 (C++23) No.3719 Share the Tree

• 問題: No.3719 Share the Tree
• ユーザー: iastm
• 提出日時: 2026-10-30 12:11:07
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 297 ms / 2,000 ms
• コード長: 3,281 bytes
• コンパイル時間: 1,387 ms
• コンパイル使用メモリ: 194,584 KB
• 実行使用メモリ: 9,780 KB
• 平均クエリ数: 2.00
• 最終ジャッジ日時: 2026-10-30 12:11:40
• 合計ジャッジ時間: 6,078 ms
• ジャッジサーバーID （参考情報）: judge4_0 / judge2_0

ファイルパターン	結果
sample	AC * 1
other	AC * 26

ソースコード

#include <iostream>
#include <vector>
// #include <kotone/pruefer>
// https://github.com/amiast/cpp-utility

#ifndef KOTONE_PRUEFER_HPP
#define KOTONE_PRUEFER_HPP

#include <vector>
#include <queue>
#include <cassert>

namespace kotone {

// Returns the Pruefer code of the specified undirected tree.
// Requires `tree` to be a valid representation of an undirected tree.
// Requires `tree.size() >= 2`.
// Requires `0 <= tree[i][j] < tree.size()` for all `0 <= i < tree.size()` and `0 <= j < tree[i].size()`.
// Reference: https://info.atcoder.jp/entry/algorithm_lectures/prufer_code
std::vector<int> encode_pruefer(const std::vector<std::vector<int>> &tree) {
    assert(int(tree.size()) >= 2);
    int n = tree.size();
    std::vector<int> deg(n);
    for (int i = 0; i < n; i++) deg[i] = tree[i].size();
    std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
    for (int i = 0; i < n; i++) if (deg[i] == 1) pq.push(i);
    std::vector<int> result;
    for (int i = 0; i < n - 2; i++) {
        int u = pq.top();
        pq.pop();
        deg[u] = 0;
        for (int v : tree[u]) {
            assert(0 <= v && v < n);
            if (deg[v] == 0) continue;
            result.push_back(v);
            if (--deg[v] == 1) pq.push(v);
        }
    }
    return result;
}

// Returns the adjacency list of the undirected tree corresponding to the specified Pruefer code.
// The order of vertices in each list is undefined.
// Requires `code` to be a valid representation of a Pruefer code.
// Requires `0 <= code[i] < code.size() + 2`.
// Reference: https://info.atcoder.jp/entry/algorithm_lectures/prufer_code
std::vector<std::vector<int>> decode_pruefer(const std::vector<int> &code) {
    int n = code.size() + 2;
    std::vector<int> count(n);
    for (int p : code) {
        assert(0 <= p && p < n);
        count[p]++;
    }
    std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
    for (int i = 0; i < n; i++) if (count[i] == 0) pq.push(i);
    std::vector<std::vector<int>> tree(n);
    for (int i = 0; i < n - 2; i++) {
        int u = pq.top();
        pq.pop();
        int v = code[i];
        tree[u].push_back(v);
        tree[v].push_back(u);
        if (--count[v] == 0) pq.push(v);
    }
    int u = pq.top();
    pq.pop();
    int v = pq.top();
    tree[u].push_back(v);
    tree[v].push_back(u);
    return tree;
}

}  // namespace kotone

#endif  // KOTONE_PRUEFER_HPP

void alice() {
    int N;
    std::cin >> N;
    std::cout << N - 2 << std::endl;
    std::vector<std::vector<int>> tree(N);
    for (int i = 1; i < N; i++) {
        int u, v;
        std::cin >> u >> v;
        u--, v--;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    for (int p : kotone::encode_pruefer(tree)) std::cout << p + 1 << ' ';
    std::cout << std::endl;
}

void bob() {
    int N;
    std::cin >> N;
    std::cout << N - 2 << std::endl;
    std::vector<int> code(N - 2);
    for (int &p : code) std::cin >> p, p--;
    auto tree = kotone::decode_pruefer(code);
    for (int i = 0; i < N; i++) {
        for (int j : tree[i]) {
            if (i < j) std::cout << i + 1 << ' ' << j + 1 << std::endl;
        }
    }
}

int main() {
    std::string S;
    std::cin >> S;
    if (S == "Alice") alice();
    else bob();
}