Submission #284014

#	Time	Username	Problem	Language	Result	Execution time	Memory
284014		aloo123	Network (BOI15_net)	C++14	0 / 100	8 ms	12032 KiB

net

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define mp make_pair
#define pb push_back
#define in insert
#define vll vector<ll>
#define endl "\n"
#define pll pair<ll,ll>
#define all(x) (x).begin() , (x).end()
#define f first
#define s second
#define pr(x) cout<<x<<endl;
#define pr2(x,y) cout<<x<<" "<<y<<endl;
#define pr3(x,y,z) cout<<x<<" "<<y<<endl;
#define prv(v) for(auto x:v) cout<<x<<" ";
#define ffs fflush(stdout);
#define int ll
#define sz(x) (ll)x.size()
using namespace std;
 
 
const ll MOD = 1e9+7;
const ll INF = 1e9;
const ll LOG = 29;
#define PI 3.141592653589793238 
 
 
long long binpow(long long a, long long b) {
     a%=MOD;    
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = (res * a);
        a = (a * a);
 
        
        b >>= 1;
    }
     res%=MOD;
    return res;
}
 
const ll N =(5e5+5);
vll adj[N];
vector<pll> ans;
ll dis[N];
void dfs(ll u,ll d,ll p){
    dis[u] = d;
    for(auto v:adj[u]){
        if(v == p) continue;
        dfs(v,d+1,u);
    }
}
 
void solve(){
    ll n;
    cin>>n;
    ll lf = 0;
    for(int i = 2;i <= n;i++){
        ll u,v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    for(int i =1;i <= n;i++){
        if(sz(adj[i]) == 1){
            lf++;
        }
    }
    dfs(1,0,-1);
    if(lf % 2 == 0){
        cout << lf/2ll << endl;
        vector<pll> gg;
        for(int i = 1;i <= n;i++){
            if(sz(adj[i]) == 1){
                gg.pb(mp(dis[i],i));
            }
        }
        sort(all(gg));
        //ll xd = lf/2ll;
        for(int i = 0;i+sz(gg)/2 < sz(gg);i++){
        ans.pb(mp(gg[i].s,gg[i + sz(gg)/2].s));
    }
        for(auto x:ans){
            cout<< x.f << ' '<< x.s <<endl;
        }
        return;
    }
 
    
    cout<<(lf+1)/2ll << endl;
    vector<pll> gg;
    for(int i = 1;i <= n;i++){
        if(sz(adj[i]) == 1){
            gg.pb(mp(dis[i],i));
        }
    }
    sort(all(gg));
    //ll xd = lf/2ll;
    for(int i = 0;i+sz(gg)/2 < sz(gg);i++){
        ans.pb(mp(gg[i].s,gg[i + sz(gg)/2].s));
    }
    // ll mid = sz(gg)/2;
    // dfs(gg[mid].s,0,-1);
    // ll ma = -1,nd =-1;
    // for(int i =1;i<=n;i++){
    //     if(sz(adj[i])  == 1 && i != gg[mid].s && dis[i] > ma){
    //         ma = dis[i];
    //         nd =i ;
    //     }
    // }
    // ans.pb(mp(nd,gg[mid].s));
    for(auto x:ans){
        cout<< x.f << ' '<< x.s <<endl;
    }
}   
 
   
 
 
 
 
 
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    
       
 
    ll t=1;
   //cin>>t;
    while(t--){
        solve();
    }    
}

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