决策是考虑进入每个点之后选子树的顺序。
子树内部显然用内部的最优方案。
然后子树之间的贡献是先走的子树的大小乘后走的子树的权值和。
所以按照子树大小除以权值和从大到小排序访问就是最优的。可以用调整法证明贪心是对的。
时间复杂度 O(nlogn)O(n\log n)O(nlogn)。
By signing up a Hydro universal account, you can submit code and join discussions in all online judging services provided by us.
Using your Hydro universal account