Submission #79559

#	Time	Username	Problem	Language	Result	Execution time	Memory
79559		IOrtroiii	Network (BOI15_net)	C++14	100 / 100	687 ms	41524 KiB

net

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

const int N = 500005;

int n;
vector<int> g[N];
vector<int> leaves;

void dfs(int u,int p) {
   bool leaf = 1;
   for (int v : g[u]) if (v != p) {
      dfs(v, u); leaf = 0;
   }
   if (leaf) leaves.push_back(u);
}

int main() {
   ios_base::sync_with_stdio(false);
   cin >> n;
   for (int i = 1; i <= n - 1; ++i) {
      int u, v; cin >> u >> v;
      g[u].push_back(v), g[v].push_back(u);
   }
   int root = -1;
   for (int i = 1; i <= n; ++i) if (g[i].size() >= 2) {
      root = i; break;
   }
   dfs(root, -1);
   int sz = leaves.size();
   cout << ((sz + 1) / 2) << '\n';
   if (sz & 1) {
      cout << leaves[sz / 2] << ' ' << root << '\n';
      for (int i = 0; i < (sz / 2); ++i) {
         cout << leaves[i] << ' ' << leaves[i + (sz / 2) + 1] << '\n';
      }
   }
   else {
      for (int i = 0; i < (sz / 2); ++i) {
         cout << leaves[i] << ' ' << leaves[i + (sz / 2)] << '\n';
      }
   }
}

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