Please explain the recurrence?
Please explain the recurrence?
Okay I’ll try to explain the approach.
The thing is that we need to find which node to make as the root , and then answer calculation is trivial.
SO we start by making 1 as the root and calculate the answer.
Now let’s say 2 was connected to 1.
child[1] is the size of subtree of 1, and child[2] is the size of subtree of 2 and ans is the calculated value.
Suppose we want to see what the answer could have been when 2 was the root.
So let’s break the link for the moment between 1 and 2.
Now while computing ans when 1 was the root, we must have added child[2] to the ans because of link of 1 and 2,
So we must do ans-=child[2].
Now the ans already contains all the children of 2 , except 1 which is the new child we just made.
So we need to add child[1] to the answer, but we can’t simply add child[1] to the answer, because in child[1] 2 is considered as the child, so we add child[1]-child[2] to the answer.
Now child[1]-child[2] = n-child[2] because 1 was the root .
So ans is updated as ans = ans+n - 2 * child[2], which generalizes to ans = ans + n -2*child[i].
Thus we do it for all the nodes by running a new dfs.
See this submission https://codeforces.com/contest/1187/submission/90855001
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.