Submission #1328417

#TimeUsernameProblemLanguageResultExecution timeMemory
1328417yus1f_mNetwork (BOI15_net)C++20
0 / 100
0 ms344 KiB
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define str string
#define pb push_back
#define pf push_front
#define in insert
#define all(v) v.begin(),v.end()
const int sz=500001,INF=1000000000;
using namespace std;
ll n,num1,num2,maxDist=-INF,node,node1,node2;
vector<ll>dist,nodes;
vector<bool>isSeen;
vector<pair<ll,ll>>ans;
vector<vector<ll>>nums;
void dfs(ll num)
{
    isSeen[num]=true;
    for(int i=0;i<nums[num].size();i++)
    {
        if(!isSeen[nums[num][i]])
        {
            dist[nums[num][i]]=dist[num]+1;
            if(dist[nums[num][i]]>maxDist)
            {
                node=nums[num][i],maxDist=dist[nums[num][i]];
            }
            dfs(nums[num][i]);
        }
    }
}
void solve()
{
    cin>>n;
    nums.resize(n+1),dist.resize(n+1),isSeen.resize(n+1);
    for(int i=0;i<n-1;i++)
    {
        cin>>num1>>num2;
        nums[num1].pb(num2),nums[num2].pb(num1);
    }
    dfs(1),node1=node;
    fill(all(dist),0),fill(all(isSeen),false),maxDist=-INF;
    dfs(node1),node2=node;
    ans.pb({min(node1,node2),max(node1,node2)});
    for(int i=1;i<=n;i++)
    {
        if(nums[i].size()==1)
        {
            if(i!=node1 && i!=node2)
            {
                nodes.pb(i);
            }
        }
    }
    for(int i=0;i<(ll)(nodes.size())-1;i++)
    {
        ans.pb({min(nodes[i],nodes[i+1]),max(nodes[i],nodes[i+1])});
    }
    cout<<ans.size()<<"\n";
    for(int i=0;i<ans.size();i++)
    {
        cout<<ans[i].first<<" "<<ans[i].second<<"\n";
    }
}
int main()
{   
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    ll t=1;
    //cin>>t;
    while(t--)
    {
        solve();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...