제출 #906132

#제출 시각아이디문제언어결과실행 시간메모리
906132dsyzNetwork (BOI15_net)C++17
0 / 100
4 ms12636 KiB
#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'; ll temp = ans.front().second; while(ans.size() >= 2){ //greedily optimal to take front and back (intution: at least one of the pair will have lca = root node) cout<<ans.front().second + 1<<" "<<ans.back().second + 1<<'\n'; ans.pop_front(); ans.pop_back(); } if(ans.size() == 1){ cout<<temp + 1<<" "<<ans.front().second + 1<<'\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...