Submission #1173195

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173195		DangKhoizzzz	Network (BOI15_net)	C++20	100 / 100	210 ms	51668 KiB

net

#include <bits/stdc++.h>
#define pii pair <int , int>
#define fi first
#define se second

using namespace std;

const int INF = 1e9;
const int maxn = 5e5 + 7;

int n , child[maxn];
vector <int> g[maxn];

pii ans[maxn];

vector <int> leaf;

void dfs(int u , int p)
{
    for(int v: g[u])
    {
        if(v == p) continue;
        child[u]++;
        dfs(v , u);
    }
    if(child[u] == 0) 
    {
        leaf.push_back(u);
    }
}

void solve()
{
    cin >> n;
    for(int i = 1; i < n; i++)
    {
        int u , v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1 , 1);
    if(child[1] == 1)
    {
        leaf.push_back(1);
    }

    int sz = leaf.size();

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

    for(int i = 0 ; i < (sz/2); i++)
    {
        cout << leaf[i] << " " << leaf[i+((sz+1)/2)] << "\n";
    }
    if(sz%2) cout<< 1 << " " << leaf[sz/2];
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

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