Submission #1220618

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220618		boclobanchat	Network (BOI15_net)	C++20	100 / 100	192 ms	49776 KiB

net

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+5;
vector<int> ds[MAXN],leaf;
void dfs(int i,int pre)
{
	for(auto v:ds[i]) if(v!=pre) dfs(v,i);
	if(ds[i].size()==1) leaf.push_back(i);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<n;i++)
    {
    	int l,r;
    	cin>>l>>r;
    	ds[l].push_back(r),ds[r].push_back(l);
	}
	for(int i=1;i<=n;i++) if(ds[i].size()>1)
	{
		dfs(i,i);
		break;
	}
	int cnt=leaf.size();
	cout<<(cnt+1)/2<<"\n";
	for(int i=0;i<cnt/2;i++) cout<<leaf[i]<<" "<<leaf[i+cnt/2]<<"\n";
	if(cnt&1) cout<<leaf[0]<<" "<<leaf[cnt-1];
}

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