小塔有一棵nnn个点的树,其中111号点是根。每个点有一个权值aia_iai。如果满足任意节点的权值大于等于其子节点的权值和,那么这棵树就是一棵奇妙树。 小塔每次操作可以选择一个点,将其权值加一。请问小塔最少需要多少次操作,才能使这棵树变成一棵奇妙树。
考虑dfs,在自底向上的过程中记录子节点的权值和。
1.如果a[u] < s,至少让a[u] == s,所以ans += s - a[u]
2.如果a[u] >= s,那么u不需要增加权值就能满足条件
本题属于以下题库,请选择所需题库进行购买
ScanQRCodePrompt
GoToPasswordLoginPrompt