2022 Niu Ke Duo School Six B-Eezie and Pie (dfs)

Title:

Sample input:

101 2twenty threetwenty four3 54 64 71 88 98 100 0 1 2 2 5 3 1 0 2

Sample output:

6 6 2 3 1 1 1 2 1 1

Title:Given a rooted tree, the root is 1, each node can be its 0 ~ 𝑑[𝑖] level ancestor contribution1 value.Find the final value of each point.

Analysis: For each child node, you can first find its first ancestor node v that cannot contribute, and reduce loss[v] by 1, then above vThe ancestor node of the node cannot get the contribution of the node, so that is to say, the loss can be uploaded, then the meaning of loss[v] means that theThe number of child nodes in the subtree rooted by v that cannot contribute to v.So we can get that the final value of each node is the number of nodes in the subtree with him as the root minus the number of child nodes in the subtree with him as the root that cannot contribute to him, that is, cnt[]+loss[]

We can directly find several levels of parent nodes of each node in the dfs process, so that we can find the d[i]+1 level father, which is theThe first ancestor node of the node that cannot contribute, the complexity of the query is log level, so the total complexity is nlogn level.

See code for details:

#include#include#include#include#include