이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<utility>
#define pb push_back
#define pii pair<int, int>
#define F first
#define S second
using namespace std;
const int N = (int)5e5 + 5;
int n , u, v, ind[N], _id = 0, root = 1;
vector<int> leafs;
vector<pii> ret;
vector<int> adj[N];
void dfs(int v,int p){
ind[v] = _id ++;
for(auto u : adj[v])if(u != p)dfs(u , v);
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 1; i < n ; i ++){
cin >> u >> v;
adj[u].pb(v);
adj[v].pb(u);
}
for(int i = 1; i <= n; i ++)if(adj[i].size() > 1)root = i;
dfs(root, root);
for(int i = 1; i <= n; i ++){
if(adj[i].size() == 1)ret.pb({ind[i], i});
}
sort(ret.begin(), ret.end());
int sz= ret.size();
cout << ((sz + 1) >> 1) << endl;
for(int i = 0; i < sz/2; i ++) cout << ret[i].S << " " << ret[i + (sz+1)/2].S << endl;
if(sz&1) cout << ret[sz/2].S << " " << root << endl;
exit(0);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |