제출 #1095444

#제출 시각아이디문제언어결과실행 시간메모리
1095444maxFedorchukNetwork (BOI15_net)C++17
100 / 100
275 ms47956 KiB
#include <bits/stdc++.h> using namespace std; const long long MX=5e5+10; vector < int > mas[MX]; vector < int > lst; void DFS(int zar,int mun) { if(mas[zar].size()==1) { lst.push_back(zar); return; } for(auto u:mas[zar]) { if(u!=mun) { DFS(u,zar); } } return; } int main() { cin.tie(0); ios_base::sync_with_stdio(0); int n; cin>>n; for(int i=1;i<n;i++) { int a,b; cin>>a>>b; mas[a].push_back(b); mas[b].push_back(a); } for(int i=1;i<=n;i++) { if(mas[i].size()>1) { DFS(i,0); break; } } vector < pair < int , int > > ans; int pol=lst.size()/2; for(int i=0;i<pol;i++) { ans.push_back({lst[i],lst[i+pol]}); } if(lst.size()%2) { ans.push_back({lst[0],lst.back()}); } cout<<ans.size()<<"\n"; for(auto [a,b]:ans) { cout<<a<<" "<<b<<"\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...