Submission #313328

#	Time	Username	Problem	Language	Result	Execution time	Memory
313328		vivaan_gupta	Network (BOI15_net)	C++14	0 / 100	9 ms	12032 KiB

net

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using ld = long double;
using db = double; 
using str = string; // yay python!
 
using pi = pair<int,int>;
using pl = pair<ll,ll>;
using pd = pair<db,db>;
 
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>; 
using vs = vector<str>;
using vpi = vector<pi>;
using vpl = vector<pl>; 
using vpd = vector<pd>; 
// pairs
#define mp make_pair
#define f first
#define s second
 
// vectors
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend() 
#define sor(x) sort(all(x)) 
#define rsz resize
#define ins insert 
#define ft front() 
#define bk back()
#define pf push_front 
#define pb push_back
#define eb emplace_back 
#define lb lower_bound 
#define ub upper_bound 
 
// loops
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
 

const ll N = 5e5+5;
vector<int> adj[N];
int dist[N];
void dfs(int u,int p,int h){
	dist[u] = h;
	for(auto v:adj[u]){
		if(v!=p){
			dfs(v,u,h+1);
		}
	}
}
bool cmp(int i,int j){
	return dist[i] < dist[j];
}
int main() {	
	// you should actually read the stuff at the bottom
		int n;
	cin >> n;
	for(int i =2;i<=n;i++){
		int u,v;
		cin>>u>>v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	dfs(1,0,0);
	int cnt = 0;
	vi le;
	for(int i = 1;i <= n;i++){
		cnt += (sz(adj[i]) == 1);
		if(sz(adj[i]) == 1)
			le.pb(i);
	}
	if(cnt%2==0){
		cnt ++ ;
		cnt /= 2;
		cout << cnt << endl;
		sort(le.begin(),le.end(),cmp);
		for(int i =0;i<cnt;i++){
			cout << le[i] << " " << le[i+(sz(le)/2)] << endl;
		}
		return 0;
	}
	sort(le.begin(),le.end(),cmp);
	cout << (cnt + 1) / 2 << endl;
	cnt ++;
	cnt /= 2;
	for(int i =0;i<cnt-1;i++){
		cout << le[i] << " " << le[i+(sz(le)/2)] << endl;
	}
	cout << le[0] << " " << le.back() << endl;
	return 0;
}
 
/* stuff you should look for
	* read the probem 3 more times in case of WA :)
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
	* DON'T GET STUCK ON ONE APPROACH
*/

• Subtask 1: 0 / 18
• Subtask 2: 0 / 45
• Subtask 3: 0 / 37