Luogu p5536 [xr-3] core city (greed + tree DP looking for the center of the tree)

【XR-3】 The core city

Title Description

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 .

Input format

first line $2$ A positive integer $n,k$.

Next $n-1$ That's ok , Each row $2$ A positive integer $u,v$, It means the first one $u$ City and the $v$ There is a length of $1$ The path of .

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 .

Output format

One line, one integer , Answer .

Examples #1

The sample input #1

6 3
1 2
2 3
2 4
1 5
5 6

Sample output #1

1

Tips

【 Sample explanation 】

made by imperial order $1,2,5$ this $3$ This city is the core city , such $3,4,6$ in addition $3$ The distance between non core cities and core cities is $1$, So the answer is $1$.

Pre knowledge ： The diameter of the tree 、 The center of the tree .

The question ：

In a tree take k Points as the core city , Distance from other points to the core city by The shortest distance to these cities s.

these There is a maximum distance in the shortest distance , Put this The maximum distance is taken as the reference value of this core urban agglomeration dist, You need to ask all the different core cities dist The smallest .

In one sentence , Before, we were looking for the center of the tree , The purpose is to find a point , Then this topic is its high configuration upgraded version , Now we are looking for a central point group .

Ideas ：

When encountering this kind of complexity problem, we should simplify it first , For example, the question asks us k city , Let's assume k by 1 What's the situation .

• obviously , When k by 1 when , The core city is Midpoint of tree , Set to u.（ Contact a question you have done before ： The center of the tree ）

When k == 1 Find the center of the tree , Put the code here , Contact what you have learned before ：

int dfs_d(int u, int father)
{
	for (int i = h[u]; ~i; i = ne[i])
	{
		int j = e[i];
		if (j == father) continue;
		int d = dfs_d(j, u) + 1;
		if (down1[u] < d) down2[u] = down1[u], down1[u] = d, p[u] = j;
		else if (down2[u] < d) down2[u] = d;
	}

	return down1[u];
}

void dfs_u(int u, int father)
{
	for (int i = h[u]; ~i; i = ne[i])
	{
		int j = e[i];
		if (j == father) continue;
		if (p[u] == j) up[j] = max(up[u], down2[u]) + 1;
		else up[j] = max(up[u], down1[u]) + 1;
		dfs_u(j, u);
	}
}

int solve1()
{
	dfs_d(1, -1);
	dfs_u(1, -1);
	int u = 0, res = inf;
	for (int i = 1; i <= n; ++i)
	{
		int tmp = max(down1[i], up[i]);
		if (res > tmp) res = tmp, u = i;
	}
	return u;	// u  Point number is the center 
}

that , about k > 1 The situation of Well ？

We draw a picture on the paper ：（ Make k = 5）

For this tree , The red dot is clearly the center of the tree , The core city should be the point in the green box .

This inspires us from From the perspective of contribution reflection ：

• To make Any non core city And this k A core city Of Maximum distance Minimum , Then we Place the core city every time , All make Current maximum -1, reduce k Time that will do .

Greedy to achieve ：

• restructure This tree , With The center of the tree u As the root node , except Root node u outside , The point with the greatest depth obviously Occupy the maximum , The greatest contribution , Let's go to it Branch / subtree In the direction of diffusion, put one The core city （ Expand from the root node ）, After expansion , The contribution of all points of the subtree to the answer -1

The above process can be directly Priority queue bfs simulation , direct Sorting processing It's fine too .

For all points, follow “dis[i] = The maximum depth you can reach down − The depth ” Sort from large to small , front k A little bit It's ours The core city 了 .

Yes, of course , Before sorting, we need use dfs From the center of the tree u Start , Preprocessing The depth of each point depth[i] and The maximum depth that can be reached maxd[i]

The code is as follows , Be careful Down the recursive and Go back up The operation of ：

void dfs1(int u, int fa)
{
	maxd[u] = depth[u];	// First pair  maxd  Assign initial value to 
	for (int i = h[u]; ~i; i = ne[i])
	{
		int j = e[i];
		if (j == fa) continue;
		depth[j] = depth[u] + 1;	// obviously 
		dfs1(j, u);
		maxd[u] = max(maxd[u], maxd[j]);	// Update when backtracking  maxd, After simulation, it is not difficult to get 
	}
}

answer by dis[k] + 1（dis Array I am from Subscript to be 0 Start saving ）

Code ：

#define _CRT_SECURE_NO_WARNINGS 1
#include <bits/stdc++.h>

using namespace std;
//#define int long long
//#define map unordered_map
struct reader {
    
	template <typename Type>
	reader& operator>> (Type& ret) {
    
		register int f = 1; ret = 0; register char ch = getchar();
		for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -f;
		for (; isdigit(ch); ch = getchar()) ret = (ret << 1) + (ret << 3) + ch - '0';
		ret *= f; return *this;
	}
} fin;

const int N = 1e5 + 10, M = N << 1, inf = 0x3f3f3f3f;
int n, k;
int h[N], e[M], ne[M], idx;
int down1[N], down2[N], up[N], p[N];
int depth[N], maxd[N];

void add(int a, int b)
{
    
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

int dfs_d(int u, int father)
{
    
	for (int i = h[u]; ~i; i = ne[i])
	{
    
		int j = e[i];
		if (j == father) continue;
		int d = dfs_d(j, u) + 1;
		if (down1[u] < d) down2[u] = down1[u], down1[u] = d, p[u] = j;
		else if (down2[u] < d) down2[u] = d;
	}

	return down1[u];
}

void dfs_u(int u, int father)
{
    
	for (int i = h[u]; ~i; i = ne[i])
	{
    
		int j = e[i];
		if (j == father) continue;
		if (p[u] == j) up[j] = max(up[u], down2[u]) + 1;
		else up[j] = max(up[u], down1[u]) + 1;
		dfs_u(j, u);
	}
}

int solve1()
{
    
	dfs_d(1, -1);
	dfs_u(1, -1);
	int u = 0, res = inf;
	for (int i = 1; i <= n; ++i)
	{
    
		int tmp = max(down1[i], up[i]);
		if (res > tmp) res = tmp, u = i;
	}
	return u;
}

void dfs1(int u, int fa)
{
    
	maxd[u] = depth[u];
	for (int i = h[u]; ~i; i = ne[i])
	{
    
		int j = e[i];
		if (j == fa) continue;
		depth[j] = depth[u] + 1;
		dfs1(j, u);
		maxd[u] = max(maxd[u], maxd[j]);
	}
}

signed main()
{
    
	int T = 1; //cin >> T;

	while (T--)
	{
    
		fin >> n >> k;
		memset(h, -1, sizeof h);
		int t = n - 1;
		for (int i = 0; i < t; ++i)
		{
    
			int u, v; fin >> u >> v;
			add(u, v), add(v, u);
		}
		int u = solve1();// Find the midpoint 
		dfs1(u, -1);
		vector<int> dis;
		for (int i = 1; i <= n; ++i)
		{
    
			dis.push_back(maxd[i] - depth[i]);
		}
		sort(dis.begin(), dis.end(), greater<int>());
		printf("%d\n", dis[k] + 1);
	}

	return 0;
}