#include "tree/pruefer-code.hpp"
#pragma once #include "../misc/rng.hpp" // input: [c \in [0, n)] * (n-2), n>=3 vector<vector<int>> pruefer_code(const vector<int>& code) { int n = code.size() + 2; assert(n > 2); vector<vector<int>> g(n); vector<int> deg(n, 1); int e = 0; for (auto& x : code) deg[x]++; set<int> ps; for (int j = 0; j < n; j++) { if (deg[j] == 1) ps.insert(j); } for (auto& i : code) { if (ps.empty()) break; int j = *begin(ps); ps.erase(j); g[i].push_back(j); g[j].push_back(i); if (deg[i] == 1) ps.erase(i); deg[i]--, deg[j]--; if (deg[i] == 1) ps.insert(i); e++; } int u = -1, v = -1; for (int i = 0; i < n; i++) { if (deg[i] == 1) (u == -1 ? u : v) = i; } assert(u != -1 and v != -1); g[u].push_back(v); g[v].push_back(u); e++; assert(e == n - 1); return g; } vector<vector<int>> random_tree(int n) { if (n <= 2) { vector<vector<int>> g(n); if (n == 2) { g[0].push_back(1); g[1].push_back(0); } return g; } vector<int> pruefer(n - 2); for (auto& x : pruefer) x = randint(0, n); return pruefer_code(pruefer); } /** * @brief Pruefer Code */
#line 2 "tree/pruefer-code.hpp" #line 2 "misc/rng.hpp" #line 2 "internal/internal-seed.hpp" #include <chrono> using namespace std; namespace internal { unsigned long long non_deterministic_seed() { unsigned long long m = chrono::duration_cast<chrono::nanoseconds>( chrono::high_resolution_clock::now().time_since_epoch()) .count(); m ^= 9845834732710364265uLL; m ^= m << 24, m ^= m >> 31, m ^= m << 35; return m; } unsigned long long deterministic_seed() { return 88172645463325252UL; } // 64 bit の seed 値を生成 (手元では seed 固定) // 連続で呼び出すと同じ値が何度も返ってくるので注意 // #define RANDOMIZED_SEED するとシードがランダムになる unsigned long long seed() { #if defined(NyaanLocal) && !defined(RANDOMIZED_SEED) return deterministic_seed(); #else return non_deterministic_seed(); #endif } } // namespace internal #line 4 "misc/rng.hpp" namespace my_rand { using i64 = long long; using u64 = unsigned long long; // [0, 2^64 - 1) u64 rng() { static u64 _x = internal::seed(); return _x ^= _x << 7, _x ^= _x >> 9; } // [l, r] i64 rng(i64 l, i64 r) { assert(l <= r); return l + rng() % u64(r - l + 1); } // [l, r) i64 randint(i64 l, i64 r) { assert(l < r); return l + rng() % u64(r - l); } // choose n numbers from [l, r) without overlapping vector<i64> randset(i64 l, i64 r, i64 n) { assert(l <= r && n <= r - l); unordered_set<i64> s; for (i64 i = n; i; --i) { i64 m = randint(l, r + 1 - i); if (s.find(m) != s.end()) m = r - i; s.insert(m); } vector<i64> ret; for (auto& x : s) ret.push_back(x); return ret; } // [0.0, 1.0) double rnd() { return rng() * 5.42101086242752217004e-20; } // [l, r) double rnd(double l, double r) { assert(l < r); return l + rnd() * (r - l); } template <typename T> void randshf(vector<T>& v) { int n = v.size(); for (int i = 1; i < n; i++) swap(v[i], v[randint(0, i + 1)]); } } // namespace my_rand using my_rand::randint; using my_rand::randset; using my_rand::randshf; using my_rand::rnd; using my_rand::rng; #line 4 "tree/pruefer-code.hpp" // input: [c \in [0, n)] * (n-2), n>=3 vector<vector<int>> pruefer_code(const vector<int>& code) { int n = code.size() + 2; assert(n > 2); vector<vector<int>> g(n); vector<int> deg(n, 1); int e = 0; for (auto& x : code) deg[x]++; set<int> ps; for (int j = 0; j < n; j++) { if (deg[j] == 1) ps.insert(j); } for (auto& i : code) { if (ps.empty()) break; int j = *begin(ps); ps.erase(j); g[i].push_back(j); g[j].push_back(i); if (deg[i] == 1) ps.erase(i); deg[i]--, deg[j]--; if (deg[i] == 1) ps.insert(i); e++; } int u = -1, v = -1; for (int i = 0; i < n; i++) { if (deg[i] == 1) (u == -1 ? u : v) = i; } assert(u != -1 and v != -1); g[u].push_back(v); g[v].push_back(u); e++; assert(e == n - 1); return g; } vector<vector<int>> random_tree(int n) { if (n <= 2) { vector<vector<int>> g(n); if (n == 2) { g[0].push_back(1); g[1].push_back(0); } return g; } vector<int> pruefer(n - 2); for (auto& x : pruefer) x = randint(0, n); return pruefer_code(pruefer); } /** * @brief Pruefer Code */