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

• 問題: No.3719 Share the Tree
• ユーザー: kwm_t
• 提出日時: 2026-09-18 23:48:51
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: TLE
• 実行時間: -
• コード長: 4,643 bytes
• コンパイル時間: 2,423 ms
• コンパイル使用メモリ: 345,452 KB
• 実行使用メモリ: 79,232 KB
• 最終ジャッジ日時: 2026-09-18 23:49:04
• 合計ジャッジ時間: 13,501 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_1

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

ソースコード

#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
// using namespace atcoder;
// using mint = modint1000000007;
// const int mod = 1000000007;
// using mint = modint998244353;
// const int mod = 998244353;
// const int INF = 1e9;
// const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i, l, r) for (int i = (l); i < (r); ++i)
#define rrep(i, n) for (int i = (n)-1; i >= 0; --i)
#define rrep2(i, l, r) for (int i = (r)-1; i >= (l); --i)
#define all(x) (x).begin(), (x).end()
#define allR(x) (x).rbegin(), (x).rend()
#define P pair<int, int>
template<typename A, typename B> inline bool chmax(A& a, const B& b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A& a, const B& b) { if (a > b) { a = b; return true; } return false; }
#ifndef KWM_T_TREE_PRUFER_HPP
#define KWM_T_TREE_PRUFER_HPP

#include <queue>
#include <vector>

namespace kwm_t::tree {

/**
 * @brief 木の隣接リストから Prüfer 列を生成する。
 *
 * 頂点番号は 0, 1, ..., n-1 とする。
 * 各ステップで、残っている葉のうち頂点番号が最小のものを削除し、
 * その葉の唯一の隣接頂点を列に追加する。
 * これを頂点が 2 個になるまで繰り返す。
 *
 * @param graph 木を表す隣接リスト。
 * @return 長さ n-2 の Prüfer 列。
 *
 * 計算量:
 *   O(n log n)
 *
 * 空間計算量:
 *   O(n)
 *
 * 制約 / 注意:
 *   - graph は単純な木でなければならない。
 *   - 頂点番号は 0 から n-1 まで連続しているものとする。
 *   - n <= 2 の場合、空列を返す。
 *
 * verified:
 *
 */
std::vector<int> prufer_encode(
	const std::vector<std::vector<int>>& graph
) {
	const int n = static_cast<int>(graph.size());

	std::vector<int> degree(n);
	std::vector<bool> removed(n, false);
	std::priority_queue<
		int,
		std::vector<int>,
		std::greater<int>
	> leaves;

	for (int v = 0; v < n; ++v) {
		degree[v] = static_cast<int>(graph[v].size());
		if (degree[v] == 1) {
			leaves.push(v);
		}
	}

	std::vector<int> code;
	code.reserve(n >= 2 ? n - 2 : 0);

	for (int i = 0; i < n - 2; ++i) {
		const int leaf = leaves.top();
		leaves.pop();
		removed[leaf] = true;

		int parent = -1;
		for (const int v : graph[leaf]) {
			if (!removed[v]) {
				parent = v;
				break;
			}
		}

		code.push_back(parent);

		--degree[parent];
		if (degree[parent] == 1) {
			leaves.push(parent);
		}
	}

	return code;
}

/**
 * @brief Prüfer 列から木を復元する。
 *
 * code の長さを n-2 とすると、n 頂点の木を復元する。
 * 頂点番号は 0, 1, ..., n-1 とする。
 *
 * 復元される木は、prufer_encode で使用している
 * 「最小番号の葉を削除する」という規約に対応する。
 *
 * @param code Prüfer 列。
 * @return 復元された木の隣接リスト。
 *
 * 計算量:
 *   O(n log n)
 *
 * 空間計算量:
 *   O(n)
 *
 * 制約 / 注意:
 *   - code の各要素は 0 以上 n-1 以下である必要がある。
 *   - n = code.size() + 2。
 *   - code が空なら 2 頂点 1 辺の木を返す。
 *
 * verified:
 *   https://cp-algorithms.com/graph/pruefer_code.html
 */
std::vector<std::vector<int>> prufer_decode(
	const std::vector<int>& code
) {
	const int n = static_cast<int>(code.size()) + 2;

	std::vector<int> degree(n, 1);

	for (const int v : code) {
		++degree[v];
	}

	std::priority_queue<
		int,
		std::vector<int>,
		std::greater<int>
	> leaves;

	for (int v = 0; v < n; ++v) {
		if (degree[v] == 1) {
			leaves.push(v);
		}
	}

	std::vector<std::vector<int>> graph(n);

	for (const int v : code) {
		const int leaf = leaves.top();
		leaves.pop();

		graph[leaf].push_back(v);
		graph[v].push_back(leaf);

		--degree[v];
		if (degree[v] == 1) {
			leaves.push(v);
		}
	}

	const int u = leaves.top();
	leaves.pop();

	const int v = leaves.top();

	graph[u].push_back(v);
	graph[v].push_back(u);

	return graph;
}

} // namespace kwm_t::tree

#endif // KWM_T_TREE_PRUFER_HPP
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	string s; cin >> s;
	int n; cin >> n;
	cout << n - 2 << endl;
	if (s == "Alice") {
		vector<vector<int>>g(n);
		rep(i, n - 1) {
			int u, v; cin >> u >> v;
			u--, v--;
			g[u].push_back(v);
			g[v].push_back(u);
		}
		auto c = kwm_t::tree::prufer_encode(g);
		for (auto e : c)cout << e + 1 << " ";
		cout << endl;
	}
	else {
		vector<int>v(n - 2);
		rep(i, n)cin >> v[i];
		auto g = kwm_t::tree::prufer_decode(v);
		rep(i, n) {
			for (auto e : g[i])if (e > i)cout << i + 1 << " " << e + 1 << endl;
		}
	}
	return 0;
}