Submission #1272903

#TimeUsernameProblemLanguageResultExecution timeMemory
1272903SP_CaramenNetwork (BOI15_net)C++20
0 / 100
2 ms14392 KiB
#include <bits/stdc++.h>
#define int long long
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FOD(i, a, b) for (int i = (a); i >= (b); i--)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define ALL(x) (x).begin(), (x).end()
#define _SP_Caramen__ signed main()
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout)
#define MASK(i) (1LL  << (i))
#define BIT(n , i) (((n) >> (i)) & 1)
#define SET_ON(n , i) ((n) | MASK(i))
#define SET_OFF(n , i) ((n) & ~MASK(i))
using namespace std;
const int MAXN = 5e5 + 5;
const int inf = 1e18;

int n;
vector<int> adj[MAXN];
vector<int> leaves;

_SP_Caramen__ {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	cin >> n;
	for (int i = 1 ; i < n ; i++ ) {
		int u , v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	for (int i = 1 ; i <= n ; i++ ) if(adj[i].size() == 1) leaves.push_back(i);
	// for (int i : leaves) cout << i << ' ';

	cout << (leaves.size() + 1) / 2 << '\n';
	for (int i = 0 ; i < leaves.size() / 2 ; i++ ) cout << leaves[i] << ' ' << leaves[leaves.size() - i - 1] << '\n';
	if(leaves.size() % 2 != 0) cout << leaves[leaves.size() / 2] << ' ' << leaves[0];

	cerr << "Time elapsed: " << TIME << "s.\n";
	return (0 ^ 0);
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...