Submission #108708

#	Time	Username	Problem	Language	Result	Execution time	Memory
108708		Mahdi_Jfri	Network (BOI15_net)	C++14	0 / 100	15 ms	12160 KiB

net

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back

const int maxn = 5e5 + 20;

vector<int> adj[maxn] , tmp;

void dfs(int v , int p = -1)
{
	if((int)adj[v].size() == 1)
		tmp.pb(v);
	for(auto u : adj[v])
		if(u != p)
			dfs(u , v);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n;
	cin >> n;

	for(int i = 0; i < n - 1; i++)
	{
		int a , b;
		cin >> a >> b;
		a-- , b--;

		adj[a].pb(b);
		adj[b].pb(a);
	}

	int root = -1;
	for(int i = 0; i < n; i++)
		if((int)adj[i].size() != 1)
		{
			root = i;
			dfs(i);
			break;
		}

	int k = tmp.size();
	cout << (k + 1) / 2 << endl;

	if(k & 1)
		cout << root + 1 << " " << tmp.back() + 1 << endl , tmp.pop_back();

	for(int i = 0; i < k / 2; i++)
		cout << tmp[i] + 1 << " " << tmp[i + k / 2] + 1 << endl;
}

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