Submission #790126

#	Time	Username	Problem	Language	Result	Execution time	Memory
790126		tch1cherin	Network (BOI15_net)	C++17	100 / 100	610 ms	51968 KiB

net

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

const int MAX_N = 500005;
vector<int> G[MAX_N];
vector<int> ord;

void DFS(int u, int p) {
  for (int v : G[u]) {
    if (v != p) {
      DFS(v, u);
    }
  }
  if (G[u].size() == 1) {
    ord.push_back(u);
  }
}

int main() {
  int N;
  cin >> N;
  for (int i = 0; i < N - 1; i++) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    G[u].push_back(v);
    G[v].push_back(u);
  }
  DFS(0, -1);
  int L = (int)ord.size();
  cout << (L + 1) / 2 << "\n";
  for (int i = 0; i < (L + 1) / 2; i++) {
    cout << 1 + ord[i] << " " << 1 + ord[i + L / 2] << "\n";
  }
}

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