Submission #1189533

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189533		hehe	Network (BOI15_net)	C++20	100 / 100	379 ms	45384 KiB

net

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

vector<vector<int>> adj(500003);
vector<int> margini;

void dfs(int node, int parent){
    if(adj[node].size() == 1){
        margini.push_back(node);
    }
    for(int i : adj[node]){
        if(i != parent){
            dfs(i, node);}
    }
}

int main(){
    int n; cin >> n;
    int a, b;
    
    for(int i = 0; i < n - 1; i++){
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    
    dfs(1, 0);
    
    int marime = margini.size();
    
    int middle = marime / 2;
    
    cout << marime / 2 + marime % 2 << '\n';
    
    for(int i = 0; i < middle; i++){
        cout << margini[i] << ' ' << margini[i + middle] << '\n';
    }
    
    if(marime % 2 == 1){
        cout << margini[0] << ' ' << margini[marime - 1];
    }
}

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