The first subtask can be solved by iterating over all choices of ~k~ parks and calculating the distances to the remaining nodes.

In the second subtask, the desired node is precisely the tree center, which can be found as one of the two central nodes on the tree diameter. The diameter of the tree can be found in a standard way, by calling a DFS two times to find the furthest node to the furthest node to some starting node.

Solving the third and fourth subtasks required binary search. In the third subtask, one iteration of binary search is just a simpler case of the general case of a tree. Therefore, we'll just describe the general case.

We do a binary search on the answer. Fix some ~r~ and now we need to determine if it's possible to place ~k~ parks so that each node has at least one park at a distance ~\le k~. We'll solve a somewhat stronger problem - we'll calculate the smallest number of parks needed to cover the entire tree, and compare this number to ~k~. Intuitively, it is not beneficial to take the leaves, but to try to take nodes as far from them as possible, but to still cover them.

The algorithm is the following: we maintain a tree of still unprocessed nodes. In each step, we choose some leaf. Call it ~u~ and let's say it's connected to a still unprocessed node ~v~. We'll update some information for ~v~ and remove ~u~. Additionally, it's possible that one of ~u~ or ~v~ is declared a park. This process is repeated until no more nodes are left.

We will refer to the nodes that were already processed and removed from the tree as being outside. The unprocessed nodes are divided up into two categories:

1. Nodes which have already been covered by someone from the outside. For such nodes, we maintain an array ~dist[x]~ representing the distance to the nearest park from the outside. This means that toward the inside, we can still cover nodes up to a distance of ~r-dist[x]~.
2. Nodes which have not yet been covered from the outside and for which we decided that they will be covered at some point in the future. For such nodes, we maintain ~reach[x]~ representing how far inward can we place a park so that it still covers ~x~ along with all the nodes we haven't yet covered and which depend on ~x~ to be covered.

At each step, we remove a leaf ~u~ and for its neighbour ~v~, we update ~dist[v]~ or ~reach[v]~. When doing this, it's possible that the category in which ~v~ belongs to changes. How to exactly update this information for ~v~ depends on a few simple cases and is left as an exercise to the reader. Let's illustrate one such case. If ~u~ and ~v~ are both already covered from the outside, and the length of the edge between them is ~w~, then we set ~dist[v]~ to ~\min(dist[v], dist[u]+w)~. What remains is to determine when a node should be declared a park. We do this when a leaf ~u~ is not covered from the outside and when ~reach[u] \le w~. If there is a strict inequality, we place a park in ~u~, and otherwise we can place it in ~v~.

The correctness of this algorithm follows from the fact that the parks are being placed at the last possible moment, i.e. when we don't have a choice. The time complexity of this procedure is ~\mathcal O(n)~, making the total complexity ~\mathcal O(n \log(n \cdot w_\max))~.