I also have a simpler looking approach: 1. Calculate the number of nodes in the subtree for each node i 2. For calculating the answer for root, also calculate the depths of each node w.r.t root and sum them up for the answer to the root 3. Now, let res be our answer array and subt be our arrays holding number of nodes in subtree of node i 4. Res[i]=res[par]+n-2*subt[i] 5. Lets suppose we know the answer for our parent, now to find the distance to its child i, we see that all nodes lying outside the subtree of i will have +1 in distance to i when compared to its par because it is 1 distance further away. So we add n-subt[i] to the answer, also we see that the result of our parent has all the nodes in subtree of i at 1 greater distance when compared to i, so we add -subt[i] to transform the result of i's parent to the result of i 6. Res[i] has final answer of i, also calculate res[i] only when i!=root ( we already calculated before at start)
looks like the problem can be solved with the rerooting technique. try thinking more in that direction. root the tree at some arbitrary node. for the root answer should be easy to evaluate using top down dp. for other nodes if I start from vertex i, i will either go downwards or upwards. downwards ans is easy. upward ans you will have to re-use the answer of parent. i might be wrong as I only had a glimpse of the problem.
@@AlgosWithKartik Yeah these problem uses the rerooting technique , I am struggling with these problem , from last two days, if you are not busy plz guide me
Best explanation I found on the topic today. How the formula of re-rooting was derived was major problem and major part.
the rerooting explanation was amazing, I was very happy when I find out the recurrence for SubAns[I] myself , , , , Thanks :)
That's amazing and I am happy to see that you are benefitting from the videos :)
This man deserves more likes and subscriptions
Bhai mazaa aa gaya yaar solve karke. Kya baat hai!
I also have a simpler looking approach:
1. Calculate the number of nodes in the subtree for each node i
2. For calculating the answer for root, also calculate the depths of each node w.r.t root and sum them up for the answer to the root
3. Now, let res be our answer array and subt be our arrays holding number of nodes in subtree of node i
4. Res[i]=res[par]+n-2*subt[i]
5. Lets suppose we know the answer for our parent, now to find the distance to its child i, we see that all nodes lying outside the subtree of i will have +1 in distance to i when compared to its par because it is 1 distance further away. So we add n-subt[i] to the answer, also we see that the result of our parent has all the nodes in subtree of i at 1 greater distance when compared to i, so we add -subt[i] to transform the result of i's parent to the result of i
6. Res[i] has final answer of i, also calculate res[i] only when i!=root ( we already calculated before at start)
Nice ! Good intuition
amazing videos bhaiya i was able to solve this problem on my own thank you for making these videos
Such a beautiful explanation as ususal
we need more tutorials on cses sets amazing explanation
Nice explanation
Do you thinking of making video explanations on Range queries also? It might be more helpful, although code forces blog is nice too
maybe not for CSES problems but I am definitely considering a series on range query DS like sparse tables segtrees sqrt decomp etc.
Thank you for such a nice explanations...
Great explanation!
clear explanation.thnx
Helpful and Great!
beautiful sir
Why does he need count of nodes present in subtree? Can somebody explain
Amazing Bhaiya :)
Damn explanation.🔥
8:06 why isnt 1+1+2+2 instead ?
See 8:43
This happens when you comment too fast😂
Awesome video
how can I solve these problem
www.hackerearth.com/practice/algorithms/graphs/depth-first-search/practice-problems/algorithm/parwal-problem/
looks like the problem can be solved with the rerooting technique. try thinking more in that direction.
root the tree at some arbitrary node. for the root answer should be easy to evaluate using top down dp.
for other nodes
if I start from vertex i, i will either go downwards or upwards. downwards ans is easy. upward ans you will have to re-use the answer of parent.
i might be wrong as I only had a glimpse of the problem.
@@AlgosWithKartik Yeah these problem uses the rerooting technique , I am struggling with these problem , from last two days, if you are not busy plz guide me
Please write what is partial, sb and other terms..The explaination is not that clear because of that
Please be more clear with what you want to say
Which part do you find is not clear and I'll try to help you with that.
@@AlgosWithKartik last part