Submission #1173181

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173181		DangKhoizzzz	Network (BOI15_net)	C++20	0 / 100	6 ms	12100 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];

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);
    }

    cout << ((int)leaf.size() + 1)/2 << '\n';

    int l = 0;
    int r = leaf.size() - 1;

    while(l < r)
    {
        cout << leaf[l] << ' ' << leaf[r] << '\n';
        l++;
        r--;
    }

    if((int)leaf.size() % 2 == 1)
    {
        cout << leaf[l] << ' ' << leaf[0] << '\n';
    }

}

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

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