Responding a year late lol but anyway, so the reason is that when he added the value of 8, it includes the distances from the node 0 to all the nodes in the sub tree of the CHILD node. However, the CHILD node is 1 unit closer to all the nodes in ITS sub tree than node 0, so you need to subtract 1 for every node within the sub tree. This value is given by count[CHILD]. If it still doesn’t make sense here’s another way of thinking about it : if I have 4 people standing in a row which are 1 meter apart, the 3rd guy is going to be 1 meter closer to the 1st and 2nd guy compared to the 4th guy. So if we measure the distances from the 4th guy to the 1st and 2nd guy, if we wanted to calculate the distance form the 3rd guy to the 1st and 2nd, you would need to subtract 2 meters from the distance given by the 4th guy to get the correct answer. Hope this helps
the magical equation is based around re-rooting and calculating the distance sums in O(1) for each child node once re-rooted. I tried to give a visual explanation here ua-cam.com/video/eZUqJq_Q_qA/v-deo.html intuitively it makes sense when you change the root you have increased some set of path sums by 1 x farther_nodes (as the root is now further away from some set of nodes) and decreased the rest of the path sums b/w the new root and all other nodes by 1 x closer_nodes the root got closer to some set of nodes
from collections import defaultdict class Solution: def sumOfDistancesInTree(self, n: int, edges: List[List[int]]) -> List[int]: graph = defaultdict(list) for n , v in edges : graph[n].append(v) graph[v].append(n) def travel(i): visited = set([i]) queue = deque([(i,0)]) output = 0 while queue: curr , dis = queue.popleft() for nx in graph[curr]: if nx not in visited: visited.add(nx) queue.append((nx,dis+1)) output += (dis+1) return output return [travel(i) for i in range(n)] Hey Timothy I am passing 6 as range in last list comprehensions but its running only twice can I know why ?
@@hunterxx6744 oh okay, i get it now. I think maybe the value of n change because you used it in the early for loop (when building the graph), .. it's only a guess
Why do you minus count[child] twice?
Responding a year late lol but anyway, so the reason is that when he added the value of 8, it includes the distances from the node 0 to all the nodes in the sub tree of the CHILD node. However, the CHILD node is 1 unit closer to all the nodes in ITS sub tree than node 0, so you need to subtract 1 for every node within the sub tree. This value is given by count[CHILD]. If it still doesn’t make sense here’s another way of thinking about it : if I have 4 people standing in a row which are 1 meter apart, the 3rd guy is going to be 1 meter closer to the 1st and 2nd guy compared to the 4th guy. So if we measure the distances from the 4th guy to the 1st and 2nd guy, if we wanted to calculate the distance form the 3rd guy to the 1st and 2nd, you would need to subtract 2 meters from the distance given by the 4th guy to get the correct answer. Hope this helps
All of these videos for 834 tell you the Magic Equation then dive straight into the implementation. But never how to derive that Magic Equation.
the magical equation is based around re-rooting and calculating the distance sums in O(1) for each child node once re-rooted. I tried to give a visual explanation here ua-cam.com/video/eZUqJq_Q_qA/v-deo.html intuitively it makes sense when you change the root you have increased some set of path sums by 1 x farther_nodes (as the root is now further away from some set of nodes) and decreased the rest of the path sums b/w the new root and all other nodes by 1 x closer_nodes the root got closer to some set of nodes
from collections import defaultdict
class Solution:
def sumOfDistancesInTree(self, n: int, edges: List[List[int]]) -> List[int]:
graph = defaultdict(list)
for n , v in edges :
graph[n].append(v)
graph[v].append(n)
def travel(i):
visited = set([i])
queue = deque([(i,0)])
output = 0
while queue:
curr , dis = queue.popleft()
for nx in graph[curr]:
if nx not in visited:
visited.add(nx)
queue.append((nx,dis+1))
output += (dis+1)
return output
return [travel(i) for i in range(n)]
Hey Timothy I am passing 6 as range in last list comprehensions but its running only twice can I know why ?
what is running twice ? And this code is not going to work anyway, you will get TLE since is quadratic time complexity
@@dumbassopinions2270 Yeah this will give TLE but in comprehensions it should call function 6 time but its calling only twice
@@hunterxx6744 oh okay, i get it now. I think maybe the value of n change because you used it in the early for loop (when building the graph), .. it's only a guess
@@dumbassopinions2270 May be I visualize
@@dumbassopinions2270 May be I will visualizw
Thank you so much! Gotta say it's the best out there
whiteboard is back
Haha I need to buy a digital one
@@timc3406 don't buy, loving this.
thnx daddy
yoo💀
WTF?