| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 715795 | Charizard2021 | Network (BOI15_net) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
const int N = 500001;
#define IOS ios::sync_with_stdio(false);; cin.tie(NULL)
bool visited[N];
int LeavesInsubtee[N];
vector<int> adj[N];
vector<int> res[N];
int n;
int ans = 0;
int cur_ans = 0;
int subtreeValue = 0;
void dfs(int u){
visited[u] = true;
if((int)adj[u].size() == 1){
LeavesInsubtee[u] = 1;
}
for(int v : adj[u]){
if(!visited[v]){
dfs(v);
LeavesInsubtee[u] += LeavesInsubtee[v];
}
}
}
void dfs2(int u){
visited[u] = true;
if((int)adj[u].size() == 1){
res[subtreeValue].push_back(u);
}
for(int v : adj[u]){
if(!visited[v]){
dfs2(v);
}
}
}
int cutlocation(int u){
visited[u] = true;
for(int v : adj[u]){
if(!visited[v]){
if(LeavesInsubtee[v] > floor((cur_ans)/2)){
return cutlocation(v);
}
}
}
return u;
}
int cut(int u){
dfs(1);
for(int i = 1; i <= n; i++){
visited[i] = false;
}
int x = cutlocation(1);
for(int i = 1; i <= n; i++){
visited[i] = false;
}
visited[x] = true;
for(int v : adj[x]){
subtreeValue++;
dfs2(v);
}
return x;
}
struct cmp{
bool operator()(const int &a, const int &b){
if(res[a].size() == res[b].size()){
return a < b;
}
return res[a].size() > res[b].size();
}
};
int main(){
IOS;
cin >> n;
for(int i = 0; i < n - 1; i++){
int a, b;
cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
for(int i = 1; i <= n; i++){
if((int)adj[i].size() == 1){
ans++;
}
}
cur_ans = ans;
ans = (ans + 1)/2;
cout << ans << "\n";
cut(n);
vector<int> finalAns(2 * ans);
vector<int> v;
set<int, cmp> s;
for(int i = 1; i <= subtreeValue; i++){
s.insert(i);
}
while(!s.empty()){
int a = *(s.begin());
s.erase(a);
v.push_back(res[a].back());
res[a].pop_back();
if(!s.empty()){
int b = *(s.begin());
s.erase(b);
v.push_back(res[b].back());
res[b].pop_back();
if(!res[b].empty()){
s.insert(b);
}
}
if(!res[a].empty()){
s.insert(a);
}
}
if(v.size() % 2 == 0){
v.push_back(res[1][0]);
}
for(int i = 0; i < (int)finalAns.size(); i += 2){
cout << finalAns[i] << " " << finalAns[i + 1] << "\n";
}
}