Submission #79548

#	Time	Username	Problem	Language	Result	Execution time	Memory
79548		IOrtroiii	Network (BOI15_net)	C++14	0 / 100	13 ms	12284 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 << root << ' ' << leaves[0] << '\n';
      for (int i = 1; i + i < sz; ++i) {
         cout << leaves[i] << ' ' << leaves[sz - i] << '\n';
      }
   }
   else {
      for (int i = 0; i + i < sz; ++i) {
         cout << leaves[i] << ' ' << leaves[sz - 1 - i] << '\n';
      }
   }
}

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