PROBLEM LINK:
Author: Alei Reyes
Primary Tester: Hussain Kara Fallah
Secondary Tester: Kacper Walentynowicz
Editorialist: Hussain Kara Fallah
DIFFICULTY:
Easy
PREREQUISITES:
Graph Theory
PROBLEM:
Construct a tree of N nodes such that the maximum distance between one of its centers and one of its centroids is exactly B.
A vertex u is a centroid if after removing u from the tree, the size of any of the resulting connected components is at most n/2.
Let f(x) be the greatest distance from u to any other vertex of the tree. A vertex u is a center if f(u) ≤ f(v) for any other vertex v.
EXPLANATION:
First of all let’s create a tree consisting of a single node numbered 1 and assuming that it will be our centroid.
Now we should construct a chain consisting of B edges ending in a node representing our future center and this node is numbered B+1. Currently our tree is composed of a chain containing B+1 nodes. Currently node B+1 is not the center of our tree. So to make it our center we should extend this chain from this node by B extra nodes. Resulting a chain consisting of 2*B+1 node where the ith node and the (i+1)th node are connected by an edge for each 0 < i < 2*B+1
Now we assured that node B+1 is our center. And clearly node 1 is not our centroid. So we must make use of the remaining nodes and attach each one of them directly to node 1 (Each of them connected to 1 by a directed edge so we keep our center unchanged). Of course we must have enough nodes to ensure that. Removing node 1 would leave us with a subtree consisting of 2*B nodes, and subtrees made of single nodes (we attached).
As a conclusion we can say that for any N,B such that :
2*B ≤ N/2 → 4*B ≤ N
A solution exists and can be constructed by this way. For cases where 4*B > N, constructing such a tree is impossible.
Of course we must handle this special case :
Case n = 2:
if B = 1 the tree made of 2 nodes connected by an edge is the solution, for other values of B the answer is NO
This image briefly describes the configuration of our tree: