제출 #79572

#제출 시각아이디문제언어결과실행 시간메모리
79572VinhspmNetwork (BOI15_net)C++14
0 / 100
15 ms12392 KiB
#include<bits/stdc++.h> using namespace std; #define fi first #define se second #define pb push_back typedef pair<int, int> ii; const int N = 5e5 + 10; const int oo = 1e9; int n; int deg[N], sz[N], tmp[N]; bool visit[N]; vector<int> lef, rig, vi[N]; void dfs(int pre, int u) { sz[u] = 1; for(int v: vi[u]) if(v != pre) dfs(u, v), sz[u] += sz[v]; // :D } void findcen(int pre, int u, int sz1, bool spm) { if(spm) visit[u] = true; if(!spm) { for(int v: vi[u]) if(v != pre && sz[v] * 2 >= sz1) { findcen(u, v, sz1, 0); return; } } visit[u] = true; for(int v: vi[u]) if(v != pre) findcen(u, v, sz1, 1); } void calc(int pos, bool spm) { int cnt = 0; for(int i = pos; i <= n; ++i) if(visit[i] == spm && deg[i] == 1) tmp[++cnt] = i; for(int i = 1; i <= cnt - 1; i += 2) cout << tmp[i] << ' ' << tmp[i + 1] << '\n'; if(cnt % 2 == 1) for(int i = 1; i <= n; ++i) if(visit[i] == 1 - spm && deg[i] == 1) { cout << i << ' ' << tmp[cnt]; exit(0); } } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; for(int i = 1; i < n; ++i) { int u, v; cin >> u >> v; vi[u].pb(v); vi[v].pb(u); deg[u] ++; deg[v] ++; } int ans = 0; for(int i = 1; i <= n; ++i) if(deg[i] == 1) ans ++; dfs(1, 1); findcen(1, 1, sz[1], 0); cout << (ans + 1) / 2 << '\n'; int ptr1 = 1, ptr2 = 1; while(visit[ptr1] || deg[ptr1] > 1) ptr1 ++; while(!visit[ptr2] || deg[ptr2] > 1) ptr2 ++; while(ptr1 <= n && ptr2 <= n) { cout << ptr1 << ' ' << ptr2 << '\n'; ptr1 ++; ptr2 ++; while((visit[ptr1] || deg[ptr1] != 1)) { ptr1 ++; if(ptr1 > n) break; } while((!visit[ptr2] || deg[ptr2] != 1)) { ptr2 ++; if(ptr2 > n) break; } } if(ptr1 <= n) calc(ptr1, 0); if(ptr2 <= n) calc(ptr2, 1); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...