제출 #821995

#제출 시각아이디문제언어결과실행 시간메모리
821995vjudge1Network (BOI15_net)C++17
100 / 100
754 ms41272 KiB
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int nmax = 500005;
vector<int>adj[nmax];
vector<int>leaf;
void DFS() {
    stack<pair<int,int>>st;
    st.push({1,0});
    while(!st.empty()) {
        int nod = st.top().fi;
        int par = st.top().se;
        st.pop();
        if(adj[nod].size()==1) leaf.push_back(nod);
        for(auto nxt:adj[nod]) {
            if(nxt != par) st.push({nxt,nod});
        }
    }

}
int main() {
    int n,a,b;
    cin >> n;
    for(int i=1; i<n; i++) {
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    DFS();
    int N = (leaf.size()+1)/2;
    cout << N << endl;
    for(int i=0; i<N; i++) {
        cout << leaf[i] << " " << leaf[i+(leaf.size()/2)] << endl;
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...