Распределить вес по краям дерева

Question

A tree with N nodes and N-1 Bidirectional edges, and given an integer S.

Now, you have to assign the weights to the edges of this tree such that: 
    1. the sum of the weights of all the edges is equal to S 
    2. for every possible diameter of the tree, the maximum weight over all the edges covered by its paths is the minimum possible.

Output this minimum possible edge weight.
The diameter of a tree is the number of nodes on the longest path between two leaves in the tree

Constraints
1 <= T <= 10
1 <= N <= 2*10^3
1 <= u,v <= N
1 <= S <= 10^9

Input Format 
The first line of the input contains an Integer T, the total number of test cases.

The first line of each test case contains two space separated integers N and
S,the number of nodes in a tree and the integer S as mentioned in the problem statement.

Then the N-1 lines follow, each containing two space-separated integers u
and v representing that there is a bidirectional edge between the nodes u and v.

Я не могу сформулировать стратегию распределения веса по всем граням заданным образом. Любая помощь очень ценится.

Answer 1

Есть два случая:

1. Если каждый край участвует хотя бы в одном диаметре, то лучшее, что вы можете сделать, - это равномерно разделить S между N - 1 ребрами. Таким образом, ответ ⌈S/(N-1)⌉. Это случай для вашего теста № 1.
2. Если существует хотя бы одно ребро, которое не участвует ни в каком диаметре, тогда вы можете распределить все S там, и ответ будет 0. Это случай ребра 1-4 в вашем тесте № 2 .

Итак, мы сократили задачу до определения всех ребер, которые не принадлежат ни к какому диаметру. Здесь хорошо написан ответ здесь .