제출 #1283499

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1283499		g4yuhg	Network (BOI15_net)	C++20	0 / 100	3 ms	332 KiB

net

#include<bits/stdc++.h>
typedef int ll;
#define pii pair<ll, ll>
#define fi first
#define se second
#define endl '\n'
#define TASK ""
#define N 500005
#define LOG 17
using namespace std;

const ll inf = 1e9;

bool ghuy4g;

ll n, r;
vector<ll> adj[N];

vector<ll> leaves;

void dfs(ll u, ll parent) {
	for (auto v : adj[u]) {
		if (v == parent) continue;
		dfs(v, u);
	}
	if (adj[u].size() == 1) {
		leaves.push_back(u);
	}
}

bool klinh;

signed main() {
   // freopen("test.inp", "r", stdin);
	//freopen("test.out", "w", stdout);
	//srand(time(0));
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
   	cin >> n;
   	for (int i = 1; i <= n - 1; i ++) {
   		ll 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() > 2) {
   			r = i;
   			break;
   		}
   	}
   	
   	dfs(r, r);
   	
   	cout << (leaves.size() + 1) / 2 << endl;
   	for (int i = 0; i < leaves.size(); i += 2) {
   		if (leaves.size() % 2 == 1 && i == leaves.size() - 1) {
   			cout << leaves[i - 1] << " " << leaves[i] << endl;
   			break;
   		}
   		cout << leaves[i] << " " << leaves[i + 1] << endl;
   	}
   	
   	
   	cerr << fabs(&klinh - &ghuy4g) / double(1024 * 1024);
}

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