#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << " " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << " " << j << " " << #i << " " << q << " " << #p << endl;
#define show4(x,y) for(auto it:x) cout << it << " "; cout << #y << endl;
typedef pair<long long,long long>pii;
typedef pair<pii,pii>pi2;
vector<int>adj[500005];
int dist[500005];
int dist2[500005];
void dfs(int index, int par, int d[]){
for(auto it:adj[index]){
if(it==par) continue;
d[it]=d[index]+1;
dfs(it,index,d);
}
}
void solve(){
int n;
cin >> n;
int temp,temp2;
for(int x=0;x<n-1;x++){
cin >> temp >> temp2;
adj[temp].push_back(temp2);
adj[temp2].push_back(temp);
}
dfs(1,-1,dist);
int maxi=0;
int a=1;
for(int x=1;x<=n;x++){
if(dist[x]>maxi){
maxi=dist[x];
a=x;
}
}
dist[a]=0;
dfs(a,-1,dist);
int b=a;
maxi=0;
for(int x=1;x<=n;x++){
if(dist[x]>maxi){
maxi=dist[x];
b=x;
}
}
vector<int>leaf;
for(int x=1;x<=n;x++){
if(adj[x].size()==1){
if(x==a||x==b) continue;
leaf.push_back(x);
}
}
vector<pii>ans;
ans.push_back({a,b});
if((int)leaf.size()%2==1){
ans.push_back({leaf.back(),a});
leaf.pop_back();
}
for(int x=1;x<(int)leaf.size();x+=2){
ans.push_back({leaf[x],leaf[x-1]});
}
cout << ans.size() << "\n";
for(auto it:ans){
cout << it.first << " " << it.second << "\n";
}
}
int32_t main(){
ios::sync_with_stdio(0);
cin.tie(0);
int t=1;
//cin >> t;
while(t--){
solve();
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
13660 KB |
Output is correct |
2 |
Correct |
3 ms |
13492 KB |
Output is correct |
3 |
Correct |
3 ms |
13656 KB |
Output is correct |
4 |
Correct |
3 ms |
13660 KB |
Output is correct |
5 |
Correct |
3 ms |
13660 KB |
Output is correct |
6 |
Correct |
3 ms |
13660 KB |
Output is correct |
7 |
Correct |
3 ms |
13656 KB |
Output is correct |
8 |
Correct |
3 ms |
13660 KB |
Output is correct |
9 |
Correct |
3 ms |
13660 KB |
Output is correct |
10 |
Correct |
3 ms |
13656 KB |
Output is correct |
11 |
Correct |
4 ms |
13452 KB |
Output is correct |
12 |
Correct |
3 ms |
13660 KB |
Output is correct |
13 |
Correct |
3 ms |
13692 KB |
Output is correct |
14 |
Correct |
3 ms |
13660 KB |
Output is correct |
15 |
Correct |
4 ms |
13660 KB |
Output is correct |
16 |
Correct |
3 ms |
13660 KB |
Output is correct |
17 |
Correct |
3 ms |
13660 KB |
Output is correct |
18 |
Incorrect |
3 ms |
13496 KB |
Breaking single line is causing network to disconnect. |
19 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
13660 KB |
Output is correct |
2 |
Correct |
3 ms |
13492 KB |
Output is correct |
3 |
Correct |
3 ms |
13656 KB |
Output is correct |
4 |
Correct |
3 ms |
13660 KB |
Output is correct |
5 |
Correct |
3 ms |
13660 KB |
Output is correct |
6 |
Correct |
3 ms |
13660 KB |
Output is correct |
7 |
Correct |
3 ms |
13656 KB |
Output is correct |
8 |
Correct |
3 ms |
13660 KB |
Output is correct |
9 |
Correct |
3 ms |
13660 KB |
Output is correct |
10 |
Correct |
3 ms |
13656 KB |
Output is correct |
11 |
Correct |
4 ms |
13452 KB |
Output is correct |
12 |
Correct |
3 ms |
13660 KB |
Output is correct |
13 |
Correct |
3 ms |
13692 KB |
Output is correct |
14 |
Correct |
3 ms |
13660 KB |
Output is correct |
15 |
Correct |
4 ms |
13660 KB |
Output is correct |
16 |
Correct |
3 ms |
13660 KB |
Output is correct |
17 |
Correct |
3 ms |
13660 KB |
Output is correct |
18 |
Incorrect |
3 ms |
13496 KB |
Breaking single line is causing network to disconnect. |
19 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
13660 KB |
Output is correct |
2 |
Correct |
3 ms |
13492 KB |
Output is correct |
3 |
Correct |
3 ms |
13656 KB |
Output is correct |
4 |
Correct |
3 ms |
13660 KB |
Output is correct |
5 |
Correct |
3 ms |
13660 KB |
Output is correct |
6 |
Correct |
3 ms |
13660 KB |
Output is correct |
7 |
Correct |
3 ms |
13656 KB |
Output is correct |
8 |
Correct |
3 ms |
13660 KB |
Output is correct |
9 |
Correct |
3 ms |
13660 KB |
Output is correct |
10 |
Correct |
3 ms |
13656 KB |
Output is correct |
11 |
Correct |
4 ms |
13452 KB |
Output is correct |
12 |
Correct |
3 ms |
13660 KB |
Output is correct |
13 |
Correct |
3 ms |
13692 KB |
Output is correct |
14 |
Correct |
3 ms |
13660 KB |
Output is correct |
15 |
Correct |
4 ms |
13660 KB |
Output is correct |
16 |
Correct |
3 ms |
13660 KB |
Output is correct |
17 |
Correct |
3 ms |
13660 KB |
Output is correct |
18 |
Incorrect |
3 ms |
13496 KB |
Breaking single line is causing network to disconnect. |
19 |
Halted |
0 ms |
0 KB |
- |