Submission #405213

#	Time	Username	Problem	Language	Result	Execution time	Memory
405213		soba	Network (BOI15_net)	C++14	100 / 100	725 ms	47776 KiB

net

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
vector<int>v[500001] , leafs;

void dfs(int node , int p )
{
    if(v[node].size()==1)
    {
        leafs.push_back(node);
    }
    for(int u : v[node])
    {
        if(u!=p)
        {
            dfs(u , node);
        }
    }
    return;
}
int main()
{
    int n  , x, y ;
    cin >>n  ;
    for(int i =  0 ; i < n-1; i++)
    {
        cin >> x >>y  ;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1 , -1);
    int sz= leafs.size();

    if(sz&1)
    {
        cout << sz/2 +1 << "\n";

    }
    else cout << sz/2 << "\n";
    for(int i = 0 ; i < (sz/2) ; i++)
    {
        cout << leafs[i] << " " << leafs[i+((sz+1)/2)] << "\n";
    }
    if(sz&1)
    {
        cout << leafs[sz/2] << " " <<1 << "\n";
    }
    return 0;
}

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