algorithm - 沿树的边缘分布重量

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 中。

因此我们将问题简化为确定不属于任何直径的所有边。有一个写得很好的答案here .