### 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 i^{th} 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: