Submission #639710

#	Time	Username	Problem	Language	Result	Execution time	Memory
639710		Wunka	Network (BOI15_net)	C++17	0 / 100	7 ms	14036 KiB

net

#include<bits/stdc++.h>
using namespace std;

const int N = 5e5 + 5; 
vector<vector<int>> graph(N); 
vector<bool> visited(N); 
vector<int>  degree(N); 
map<int, int> leaf; 
int k = 0, mx, x; 

void dfs(int v) {
    visited[v] = true; 
    if(degree[v] == 1) {
        leaf[k] = v; 
        k++; 
    }

    for(int next : graph[v]) {
        if(!visited[next]) {
            dfs(next); 
        }
    }
}

int main() {
    int n; 
    cin >> n; 
    
    mx = 0; 
    for(int i = 0; i < n - 1; i++) {
        int a, b; 
        cin >> a >> b; 
        a--, b--; 
        degree[a]++, degree[b]++; 
        graph[a].push_back(b);
        graph[b].push_back(a);
        if(degree[a] > mx) {
            mx = degree[a]; 
            x = a; 
        }
        if(degree[b] > mx) {
            mx = degree[b]; 
            x = b; 
        }
    }

    dfs(x); 
    cout << (k + 1) / 2 << endl; 
    /*
    if(k % 2 == 1) {
        cout << x + 1 << ' ' << leaf[k] + 1 << '\n'; 
        k--; 
    }
    */

    for(int i = 0; i < k - i - 1; i++) {
        cout << leaf[i] + 1 << ' ' << leaf[k - i - 1] + 1 << endl; 
    }

    if(k % 2 == 1) {
        cout << leaf[k / 2] + 1 << ' ' << x + 1 << endl; 
    } 
}

• Subtask 1: 0 / 18
• Subtask 2: 0 / 45
• Subtask 3: 0 / 37