Submission #1328433

#TimeUsernameProblemLanguageResultExecution timeMemory
1328433yus1f_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,dist,maxDist,node1,node2,idx,d[sz],parent[sz][21];
vector<ll>nodes;
vector<bool>isSeen,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]])
        {
            parent[nums[num][i]][0]=num,d[nums[num][i]]=d[num]+1;
            dfs(nums[num][i]);
        }
    }
}
ll lca(ll num1,ll num2)
{
    if(d[num1]<d[num2])
    {
        swap(num1,num2);
    }
    for(int i=20;i>=0;i--)
    {
        if(d[num1]-pow(2,i)>=d[num2])
        {
            num1=parent[num1][i];
        }
    }
    if(num1==num2)
    {
        return num1;
    }
    else
    {
        for(int i=20;i>=0;i--)
        {
            if(parent[num1][i]!=parent[num2][i])
            {
                num1=parent[num1][i],num2=parent[num2][i];
            }
        }
        return parent[num1][0];
    }
}
void solve()
{
    cin>>n;
    nums.resize(n+1),isSeen.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);
    for(int i=1;i<=20;i++)
    {
        for(int j=1;j<=n;j++)
        {
            parent[j][i]=parent[parent[j][i-1]][i-1];
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(nums[i].size()==1)
        {
            nodes.pb(i);
        }
    }
    for(int i=0;i<nodes.size();i++)
    {
        if(!IsSeen[i])
        {
            maxDist=-INF;
            for(int j=0;j<nodes.size();j++)
            {
                if(i!=j && !IsSeen[j])
                {
                    dist=d[nodes[i]]+d[nodes[j]]-2*d[lca(nodes[i],nodes[j])];
                    if(dist>maxDist)
                    {
                        node1=nodes[i],node2=nodes[j],idx=j,maxDist=dist;
                    }
                }
            }
            ans.pb({min(node1,node2),max(node1,node2)}),IsSeen[i]=true,IsSeen[idx]=true;
        }
    }
    for(int i=0;i<nodes.size();i++)
    {
        if(!IsSeen[i])
        {
            maxDist=-INF;
            for(int j=0;j<nodes.size();j++)
            {
                if(i!=j)
                {
                    dist=d[nodes[i]]+d[nodes[j]]-2*d[lca(nodes[i],nodes[j])];
                    if(dist>maxDist)
                    {
                        node1=nodes[i],node2=nodes[j],idx=j,maxDist=dist;
                    }
                }
            }
            ans.pb({min(node1,node2),max(node1,node2)});
            break;
        }
    }
    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...