이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (500005)
ll N, cnt = 0;
ll pre[MAXN];
vector<ll> v[MAXN];
bool leaf[MAXN];
void dfs(ll x,ll p){
pre[x] = cnt++;
ll children = 0;
for(auto u : v[x]){
if(u != p){
dfs(u,x);
children++;
}
}
if(children == 0){
leaf[x] = 1;
}
}
int main() {
ios_base::sync_with_stdio(false);cin.tie(0);
cin>>N;
for(ll i = 0;i < N - 1;i++){
ll a,b;
cin>>a>>b;
a--, b--;
v[a].push_back(b);
v[b].push_back(a);
}
dfs(0,-1);
deque<pair<ll,ll> > ans;
for(ll i = 0;i < N;i++){
if(i == 0 && v[0].size() == 1){ //technically the root node can also be a "leaf" if rooted differently
ans.push_back({pre[i],i});
}else if(leaf[i]){
ans.push_back({pre[i],i});
}
}
sort(ans.begin(),ans.end());
cout<<(ans.size() + 1) / 2<<'\n';
for(ll i = 0;i < ll((ans.size() + 1) / 2);i++){ //greedily optimal to pair front and middle (intution: at least one of the pair will have lca = root node)
cout<<ans[i].second + 1<<" "<<ans[i + (ans.size() / 2)].second + 1<<'\n';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |