Submission #292141

#	Time	Username	Problem	Language	Result	Execution time	Memory
292141		davooddkareshki	Network (BOI15_net)	C++17	100 / 100	1206 ms	64584 KiB

net

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define F first
#define S second
#define pii pair<int,int>
#define mpr make_pair

typedef long long ll;
//typedef long double ld;

const int maxn = 5e5+10;
const int mod = 1e9+7;
const int inf = (1ll<<40)-1;

int n, m, k;
int st[maxn], par[maxn], tin[maxn], tim, cent;
vector<int> ve, g[maxn];
int num_of_leaf;
void dfs(int v)
{
    if(g[v].size() == 1)
    {
        ve.push_back(v);
        tin[v] = tim++;
    }

    int mx = 0;
    if(g[v].size() == 1) st[v] = 1;
    else                 st[v] = 0;

    for(auto u : g[v])
        if(u != par[v])
        {
            par[u] = v;
            dfs(u);
            mx = max(mx,st[u]);
            st[v] += st[u];
        }
    mx = max(mx, num_of_leaf-st[v]);
    if(mx <= num_of_leaf/2) cent = v;
}

signed main()
{
    //ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin>> n;
    for(int i = 1, u, v; i < n; i++)
    {
        cin>> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    for(int v = 1; v <= n; v++) if(g[v].size() == 1) num_of_leaf++;
    dfs(1);
    ve.clear();
    tim = 0;
    par[cent] = 0;

    dfs(cent);
    int m = num_of_leaf; /// = ve.size()
    if(m%2 == 0)
    {
        cout<< m/2 <<"\n";
        for(int i = 0; i < m/2; i++)
            cout<< ve[i] <<" "<< ve[i+m/2] <<"\n";
    }
    else
    {
        cout<< (m+1)/2 <<"\n";
        for(int i = 0; i < (m+1)/2; i++)
            cout<< ve[i] <<" "<< ve[i+m/2] <<"\n";
    }
}
/*
8
1 2
2 3
3 4
4 5
3 6
3 7
3 8
*/

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