이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define FOR(i,N) for(i=0;i<(N);++i)
#define FORe(i,N) for(i=1;i<=(N);++i)
#define FORr(i,a,b) for(i=(a);i<(b);++i)
#define FORrev(i,N) for(i=(N);i>=0;--i)
#define F0R(i,N) for(int i=0;i<(N);++i)
#define F0Re(i,N) for(int i=1;i<=(N);++i)
#define F0Rr(i,a,b) for(ll i=(a);i<(b);++i)
#define F0Rrev(i,N) for(int i=(N);i>=0;--i)
#define all(v) (v).begin(),(v).end()
#define dbgLine cerr<<" LINE : "<<__LINE__<<"\n"
#define ldd long double
using namespace std;
const int Alp = 26;
const int __PRECISION = 9;
const int inf = 1e9 + 8;
const ldd PI = acos(-1);
const ldd EPS = 1e-7;
const ll MOD = 1e9 + 7;
const ll MAXN = 5e5 + 5;
const ll ROOTN = 320;
const ll LOGN = 18;
const ll INF = 1e18 + 1022;
int N;
vi leaf, g[MAXN];
void dfs(int a, int par)
{
if(g[a].size() == 1)
leaf.pb(a);
for(int b : g[a])
if(b != par)
dfs(b, a);
}
signed main()
{
/*
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
*/
cin>>N;
F0R(i, N-1)
{
int j, k;
cin>>j>>k;
g[j].pb(k);
g[k].pb(j);
}
if(N == 2)
{
cout<<"1\n1 2\n";
exit(0);
}
int leafCount = 0, r = 0;
F0Re(i, N)
if(g[i].size() == 1)
++leafCount;
else
r = i;
dfs(r, -1);
if(leafCount%2)
leaf.pb(r);
cout<<(leafCount+1)/2<<'\n';
F0R(i, (leafCount+1)/2)
cout<<leaf[i]<<' '<<leaf[i + (leafCount + 1)/2]<<'\n';
return 0;
}
/*
8
1 2
2 3
3 4
4 5
3 6
3 7
3 8
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |