제출 #1328413

#제출 시각아이디문제언어결과실행 시간메모리
1328413yus1f_mNetwork (BOI15_net)C++20
0 / 100
1 ms436 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,maxDist1=-INF,maxDist2=-INF,node1,node2;
vector<ll>dist1,dist2,nodes;
vector<bool>isSeen1,isSeen2;
vector<pair<ll,ll>>ans;
vector<vector<ll>>nums;
void dfs1(ll num)
{
    isSeen1[num]=true;
    for(int i=0;i<nums[num].size();i++)
    {
        if(!isSeen1[nums[num][i]])
        {
            dist1[nums[num][i]]=dist1[num]+1;
            if(dist1[nums[num][i]]>maxDist1)
            {
                node1=nums[num][i],maxDist1=dist1[nums[num][i]];
            }
            dfs1(nums[num][i]);
        }
    }
}
void dfs2(ll num)
{
    isSeen2[num]=true;
    for(int i=0;i<nums[num].size();i++)
    {
        if(!isSeen2[nums[num][i]])
        {
            dist2[nums[num][i]]=dist2[num]+1;
            if(dist2[nums[num][i]]>maxDist2)
            {
                node2=nums[num][i],maxDist2=dist2[nums[num][i]];
            }
            dfs2(nums[num][i]);
        }
    }
}
void solve()
{
    cin>>n;
    nums.resize(n+1),dist1.resize(n+1),dist2.resize(n+1),isSeen1.resize(n+1),isSeen2.resize(n+1);
    for(int i=0;i<n-1;i++)
    {
        cin>>num1>>num2;
        nums[num1].pb(num2),nums[num2].pb(num1);
    }
    dfs1(1),dfs2(node1);
    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<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...