제출 #1357641

#제출 시각아이디문제언어결과실행 시간메모리
1357641jumpNetwork (BOI15_net)C++20
0 / 100
5 ms344 KiB
#include <bits/stdc++.h>
#define int long long
int n;
std::vector<int> adj[500010],node[500010];
int leaf[500010],a[500010];
int root=1,cnt=0,cnt2=0;
void get_leaf(int curr,int par){
  int sum = adj[curr].size()==1;
  for(auto to:adj[curr]){
    if(par==to)continue;
    get_leaf(to,curr);
    sum += leaf[to];
  }
  leaf[curr]=sum;
}
void get_add(int x, int par){
  if(adj[x].size()==1){
    node[cnt].push_back(x);
    return;
  }
  for(auto i:adj[x]){
    if (i!=par){
      get_add(i, x);
    }
  }
}
int centroid(int curr,int par){
  for(auto to:adj[curr]){
    if(par==to)continue;
    if(leaf[to]>leaf[root]/2)return centroid(to,curr);
  }
  if (curr!=par&&leaf[root]-leaf[curr]>leaf[curr]/2)
    return centroid(curr,par);
  return curr;
}
signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cin >> n;
  for(int i=0;i<n-1;i++){
    int a,b;
    std::cin >> a >> b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  for(int i=1;i<=n;i++)if(adj[i].size()>1)root=i;
  get_leaf(root,root);
  int cen=centroid(root,root);
  for(auto i:adj[cen]){
    ++cnt;
    get_add(i,cen);
  }
  for(int i=1;i<=cnt;i++){
    for(auto j:node[i]){
      a[++cnt2]=j;
    }
  }
  std::cout << (cnt2-1)/2+1<<'\n';
  for(int i=1;i<=cnt2;i++){
    std::cout << a[i];
    if(i%2==1)std::cout << ' ';
    else std::cout << '\n';
  }
  if(cnt2%2==1)std::cout << a[1] << '\n';
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…