Submission #1294616

#TimeUsernameProblemLanguageResultExecution timeMemory
1294616trantrungkeinNetwork (BOI15_net)C++20
0 / 100
3 ms14404 KiB
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>> ans;
vector<int> node;
const int N = 5e5 + 7;
vector<int> g[N];
int deg[N],n;
void dfs(int u, int p){
    if(deg[u] == 1){
        if(node.size() >= 2) ans.push_back({u,node.back()}), node.pop_back();
        else node.push_back(u);
    }
    for(int v : g[u]) if(v != p){
        dfs(v,u);
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i = 1; i < n; i++){
        int u,v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
        deg[u]++; deg[v]++;
    }
    int root = 1;
    for(int i = 1; i <= n; i++) if(deg[i] != 1) root = i;
    dfs(root,0);
    if(node.size() == 2){
        ans.push_back({node[0],node[1]});
        node.clear();
    }
    while(!node.empty()){
        ans.push_back({node.back(),root});
        node.pop_back();
    }
    cout << ans.size() <<'\n';
    for(auto [u,v] : ans) cout << u <<' ' << v << '\n';
}


#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...