제출 #91041

#제출 시각아이디문제언어결과실행 시간메모리
91041sjhuang26Network (BOI15_net)C++14
100 / 100
966 ms142576 KiB
#include<iostream> #include<vector> using namespace std; vector<int>s; vector<vector<int>>t;//1 IDX bool f[500005]={}; int N; void dfs(int u){ if(f[u])return; f[u]=1; if(t[u].size()==1)s.push_back(u); for(int&i:t[u])dfs(i); } int main(){ cin>>N; for(int i=0;i<=N+5;++i)t.push_back(vector<int>()); for(int i=0;i<N-1;++i){ int a,b;cin>>a>>b; t[a].push_back(b); t[b].push_back(a); } dfs(1); int k=s.size(); if(k%2){ cout<<k/2+1<<'\n'; for(int i=0;i<k/2;++i){ cout<<s[i]<<' '<<s[i+k/2+1]<<'\n'; } cout<<s[k/2]<<' '<<1<<'\n'; }else{ cout<<k/2<<'\n'; for(int i=0;i<k/2;++i){ cout<<s[i]<<' '<<s[i+k/2]<<'\n'; } } // free memory vector<vector<int>>().swap(t); vector<int>().swap(s); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...