Submission #1345466

#TimeUsernameProblemLanguageResultExecution timeMemory
1345466SzymonKrzywdaNetwork (BOI15_net)C++20
100 / 100
192 ms66252 KiB
#include <iostream>
#include <vector>

using namespace std;
using vi = vector<int>;
using pii = pair<int, int>;
using vpii = vector<pii>;
const int MAXN = 5e5 + 7;
vi graf[MAXN];
int lisc[MAXN]; //lisc w spojnej
vpii wybory[MAXN];
int rep[MAXN];
vi liscie;



int find(int v) {
    if (rep[v] == v) return rep[v];
    rep[v] = find(rep[v]);
    return rep[v]; 
}


#define ff first 
#define ss second 


void onion(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) return;

    if (wybory[a].size() > wybory[b].size()) swap(a, b);
    rep[a] = b;

    if (lisc[a] && lisc[b]) {
        wybory[a].push_back({lisc[a], lisc[b]});
        lisc[b] = 0;
        lisc[a] = 0;
    }
    else if (lisc[a]) lisc[b] = lisc[a];
    
    if (wybory[b].size() && wybory[a].size()) {
        swap(wybory[b][0].ff, wybory[a][0].ff);
    }

    for (auto & val : wybory[a]) {
        wybory[b].push_back(val);
    }



} 
/*
6
1 2
2 3
2 4
5 4
6 4
*/


void dfs(int v, int p) {
    rep[v] = v;
    if (graf[v].size() == 1) {
        lisc[v] = v;
        liscie.push_back(v);
    }
    for (int s : graf[v]) {
        if (s == p) continue;
        dfs(s, v);
        onion(v, s);
    }
    
}



int main() {
    ios_base::sync_with_stdio(0);   
    cin.tie(0);
    int n;
    cin >> n;

    int a, b;
    for (int i = 0; i < n - 1; i++) {
        cin >> a >> b;
        graf[a].push_back(b);
        graf[b].push_back(a);
    }
    dfs(1, 1);

    int rep1 = find(1);

    vpii ans = wybory[rep1];


    if (lisc[rep1]) {
        if (lisc[rep1] != liscie[0]) ans.push_back({lisc[rep1], liscie[0]});
        else ans.push_back({lisc[rep1], liscie[1]});
    }


    cout << ans.size() << '\n';
    for (auto val : ans) {
        cout << val.ff << ' ' << val.ss << '\n';
    }

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...