Multiple subtrees

CAN ANYONE EXPAIN ME THE BELOW PROBLEM (COPY PASTED FROM HACKEREARTH)

LINK:https://www.hackerearth.com/practice/algorithms/graphs/depth-first-search/practice-problems/algorithm/destructive-tree-explosion-45170564/description/

You are given a tree (not necessarily binary) with a special property which is, forming multiple sub-trees.
This happens as follows:
A random node of the tree is broken. After this, the node along with its immediate parents up to the root vanishes from the tree.
The tree has N number of nodes and nodes are numbered from 1 to N . The root of the tree is numbered as 1 .

Given the number on one of its node, you have to tell the number of sub-trees that would be formed in-case the node is broken.

THE EDITORIAL DOES NOT EXPLAIN THE SOLUTION.IT CONSISTS ONLY OF CODE.
CAN ANOYONE HELP ME WITH THIS.

all queries are independent . hence if u remove any node. and then see the tree. so u see clearly if you remove one child from the ancestor of that given node and add the children of that nodes u will get your answer.
hence u can maintain one dp array in which dp[i] wil stores total children from root node to node i.
and maintain one level array then simply add and then subtract.

1 Like