Luogu p5536 [xr-3] core city solution

Luogu P5536 【XR-3】 The core city Answer key

Topic link ：P5536 【XR-3】 The core city

The question ：

X State-owned $n$ city ,$n-1$ The length of the bar is $1$ The path of , Each road connects two cities , And any two cities can reach each other through several roads , obviously , Cities and roads form a tree .

X The king of the Kingdom decided to $k$ The city was officially designated X The core city of , this $k$ This city needs to meet the following two conditions ：

1. this $k$ The city can pass through roads , Arrive in pairs without passing through other cities .
2. Define a non core city and this $k$ The distance between the core cities is , This city and $k$ The minimum distance between two core cities . So in all non core cities , The city with the greatest distance from the core city , Its distance from the core city is the smallest . You need to find this minimum .

Data range ：

• $1\le k<n\le 10^5$.
• $1\le u,v\le n,u\ne v$, Ensure that the city and the road form a tree .

Don't be fooled by the tree , In fact, it has nothing to do with trees

Let's analyze it sensibly , These core cities must be in the middle

Then the distance between these core cities and all edge nodes is no more than $1$ Of

Then can we eliminate the tree from the outside

Then delete one by one , In the end $k$ A little bit , Is the core city

What is it? ？ Topological sort, right

Time complexity $O(n)$

Code ：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <queue>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e5+15)

queue<int> q;
struct Edge{
    int u,v,next;}e[N<<1];
int n,k,in[N],head[N],pos=1,ans=0,dep[N],vis[N];
void addEdge(int u,int v)
{
    
    e[++pos]={
    u,v,head[u]};
    head[u]=pos;++in[v];
}
void topo()
{
    
    while(!q.empty())
    {
    
        int u=q.front();q.pop();
        for(int i=head[u]; i; i=e[i].next)
        {
    
            int v=e[i].v;
            if(--in[v]!=1)continue;
            if(!vis[v])
            {
    
                vis[v]=1;
                dep[v]=dep[u]+1;
                ans=max(ans,dep[v]);
                q.push(v);--k;
                if(k<1)return;
            }
        }
    }
}
signed main()
{
    
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> k; k=n-k; //  Change the meaning 
    for(int i=1,u,v; i<n; i++)
    {
    
        cin >> u >> v;
        addEdge(u,v);addEdge(v,u);
    }
    for(int i=1; i<=n; i++)
        if(in[i]==1&&k>=1)
        {
    
            q.push(i);vis[i]=1;
            --k;ans=1;dep[i]=1;
        }
    if(k)topo();
    cout << ans << '\n';
    return 0;
}

Reprint please explain the source