제출 #1350335

#제출 시각아이디문제언어결과실행 시간메모리
1350335Zone_zoneeNetwork (BOI15_net)C++20
100 / 100
152 ms49732 KiB
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5+10;

vector<int> leaf, adj[N];
void dfs(int u, int p){
    if(adj[u].size() == 1) leaf.push_back(u);
    for(int v : adj[u]){
        if(v == p) continue;
        dfs(v, u);
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for(int i = 1; i < n; ++i){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1, -1);
    cout << (int(leaf.size())+1)/2 << '\n';
    if(int(leaf.size())&1) leaf.push_back(leaf.front());
    int l = 0, r = int(leaf.size())/2;
    while(r < leaf.size()){
        cout << leaf[l++] << ' ' << leaf[r++] << '\n';
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...