제출 #107936

#제출 시각아이디문제언어결과실행 시간메모리
107936shash42Network (BOI15_net)C++11
100 / 100
971 ms73160 KiB
#include<bits/stdc++.h> #define pb push_back #define mp make_pair #define pii pair<int, int> using namespace std; const int N=5e5+5; int n, tmr=0; vector<int> adj[N], lvlst[N]; vector< pii > ans; int lv[N], p[N]; struct lvsrt { bool operator()(const int &a, const int &b) { return lv[a]>lv[b]; } }; void dfs(int u) { for(auto &v: adj[u]) { if(v!=p[u]) { p[v]=u; dfs(v); lv[u]+=lv[v]; } } if(adj[u].size()==1 && u!=1) { tmr++; lv[u]=1; } } int findg(int u) { //cout << tmr << " finding g: " << u << endl; for(auto &v: adj[u]) { if(lv[v]>tmr/2 && p[u]!=v) { return findg(v); } } return u; } void findlvs(int u, int subt) { for(auto &v: adj[u]) { if(v!=p[u]) { p[v]=u; findlvs(v, subt); } } if(adj[u].size()==1) { lvlst[subt].pb(u); } } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n; for(int i = 1; i < n; i++) { int u, v; cin >> u >> v; adj[u].pb(v); adj[v].pb(u); } p[1]=1; dfs(1); if(adj[1].size()==1) tmr++; int g=findg(1); // cout << g; sort(adj[g].begin(), adj[g].end(), lvsrt()); memset(p, 0, n+1); int numsubt=adj[g].size(); for(int i = 0; i < numsubt; i++) { p[adj[g][i]]=g; findlvs(adj[g][i], i); } int itr=0; for(int i = 0; i < tmr/2; i++) ans.pb(mp(0, 0)); bool chk=false; for(int i = 0; i < numsubt; i++) { for(auto &v: lvlst[i]) { if(!chk && itr==tmr/2) { itr=0; chk=true; } if(!chk) ans[itr].first=v; else ans[itr].second=v; if(chk && itr==tmr/2) break; itr++; } } if(tmr%2) { ans.pb(mp(g, lvlst[numsubt-1].back())); } cout << ans.size() << "\n"; for(auto &v: ans) { cout << v.first << " " << v.second << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...