제출 #436733

#제출 시각아이디문제언어결과실행 시간메모리
436733ak2006Network (BOI15_net)C++14
0 / 100
11 ms15948 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using vb = vector<bool>; using vvb = vector<vb>; using vi = vector<int>; using vvi = vector<vi>; using vl = vector<ll>; using vvl = vector<vl>; using vc = vector<char>; using vvc = vector<vc>; using vs = vector<string>; const ll mod = 1e9 + 7,inf = 1e18; #define pb push_back #define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); void setIO() { fast; } int n = 5e5 + 5,t; vvi adj(n); vi in(n),out(n),leaves; void dfs(int u,int p) { in[u] = ++t; for (int v:adj[u])if (v != p) dfs(v,u); out[u] = ++t; if (adj[u].size() == 1)leaves.pb(u);//leaves includes the root } bool cmp(int a,int b) { return out[a] < out[b]; } int main() { setIO(); cin>>n; for (int i = 0;i<n - 1;i++){int u,v;cin>>u>>v;adj[u].pb(v),adj[v].pb(u);} dfs(1,-1); sort(leaves.begin(),leaves.end(),cmp); int ans = (int)leaves.size(); ans = (ans%2 == 1 ? ans/2 + 1 : ans/2); cout<<ans<<'\n'; for (int i = 0;i<(int)leaves.size() - 1;i+=2) cout<<leaves[i]<<" "<<leaves[i + 1]<<'\n'; if ((int)leaves.size()%2 == 1) cout<<leaves[(int)leaves.size() - 2]<<" "<<leaves[(int)leaves.size() - 1]; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...