Submission #911534

#	Time	Username	Problem	Language	Result	Execution time	Memory
911534		12345678	Network (BOI15_net)	C++17	100 / 100	732 ms	79368 KiB

net

#include <bits/stdc++.h>

using namespace std;

const int nx=5e5+5;
int n, u, v, st, sz[nx], c, res, lsz;
vector<int> d[nx], l[nx];
priority_queue<pair<int, int>> pq;
vector<pair<int, int>> ans;

int dfssz(int u, int p)
{
    sz[u]=(d[u].size()==1);
    for (auto v:d[u]) if (v!=p) sz[u]+=dfssz(v, u);
    return sz[u];
}

int findcentroid(int u, int p, int rtsz)
{
    for (auto v:d[u]) if (v!=p&&sz[v]*2>rtsz) return findcentroid(v, u, rtsz);
    return u;
}

void dfsadd(int u, int p, vector<int> &x)
{
    if (d[u].size()==1) x.push_back(u);
    for (auto v:d[u]) if (v!=p) dfsadd(v, u, x); 
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=0; i<n-1; i++) cin>>u>>v, d[u].push_back(v), d[v].push_back(u);
    for (int i=1; i<=n; i++) if (d[i].size()>1) st=i;
    c=findcentroid(st, st, dfssz(st, st));
    for (auto v:d[c]) dfsadd(v, c, l[v]);
    for (auto v:d[c]) pq.push({l[v].size(), v}), lsz+=l[v].size();
    cout<<(lsz+1)/2<<'\n';
    while (!pq.empty())
    {
        if (pq.size()>1)
        {
            auto f=pq.top().second;
            pq.pop();
            auto s=pq.top().second;
            pq.pop();
            ans.push_back({l[f][l[f].size()-1], l[s][l[s].size()-1]});
            l[f].pop_back(); l[s].pop_back();
            if (!l[f].empty()) pq.push({l[f].size(), f});
            if (!l[s].empty()) pq.push({l[s].size(), s});
        }
        else 
        {
            auto f=pq.top().second;
            ans.push_back({c, l[f][0]});
            pq.pop();
        }
    }
    //cout<<ans.size()<<'\n';
    for (auto [x, y]:ans) cout<<x<<' '<<y<<'\n';
}

/*
4
1 3
2 3
3 4
*/

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