이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |