Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Sum of Distances in Tree
Bookmark
Brute Force
Rerooting
Input
Standard
Small
Path
Custom
n
=
6
,
edges
=
[[0,1],[0,2],[2,3],[2,4],[2,5]]
0
root
1
2
3
4
5
setup
answer[0] = 0
dist
0
0
1
0
2
0
3
0
4
0
5
0
answer
0
0
1
0
2
0
3
0
4
0
5
0
root at
0
· count[] = subtree sizes · answer[] = distance sums
0
root
1
2
3
4
5
setup
answer[0] = 0
dist
0
0
1
0
2
0
3
0
4
0
5
0
answer
0
0
1
0
2
0
3
0
4
0
5
0
root at
0
· count[] = subtree sizes · answer[] = distance sums
0
root
1
2
3
4
5
Pass 1 · post-order
answer[0] = 0
dist
0
0
1
1
2
1
3
2
4
2
5
0
answer
0
0
1
0
2
0
3
0
4
0
5
0
neighbour
5
of node
2
0
root
1
2
3
4
5
Pass 1 · post-order
answer[0] = 8
dist
0
1
1
0
2
0
3
0
4
0
5
0
answer
0
8
1
0
2
0
3
0
4
0
5
0
neighbour
1
of node
0
0
root
1
2
3
4
5
Pass 1 · post-order
answer[0] = 8
dist
0
1
1
0
2
2
3
3
4
3
5
3
answer
0
8
1
0
2
0
3
0
4
0
5
0
neighbour
2
of node
5
0
root
1
2
3
4
5
Pass 1 · post-order
answer[0] = 8
dist
0
1
1
2
2
0
3
1
4
1
5
1
answer
0
8
1
12
2
0
3
0
4
0
5
0
neighbour
2
of node
3
0
root
1
2
3
4
5
Pass 1 · post-order
answer[0] = 8
dist
0
2
1
0
2
1
3
0
4
0
5
0
answer
0
8
1
12
2
6
3
0
4
0
5
0
dist[
-1
] = dist[
2
] + 1 =
0
root
1
2
3
4
5
Pass 1 · post-order
answer[0] = 8
dist
0
2
1
3
2
1
3
0
4
2
5
2
answer
0
8
1
12
2
6
3
10
4
0
5
0
answer[
3
] =
10
0
root
1
2
3
4
5
Pass 1 · post-order
answer[0] = 8
dist
0
2
1
3
2
1
3
2
4
0
5
2
answer
0
8
1
12
2
6
3
10
4
0
5
0
node
3
sits
2
step(s) from the source
0
root
1
2
3
4
5
Pass 1 · post-order
answer[0] = 8
dist
0
2
1
0
2
1
3
0
4
0
5
0
answer
0
8
1
12
2
6
3
10
4
10
5
0
neighbour
3
of node
2
0
root
1
2
3
4
5
done
answer[0] = 8
dist
0
2
1
3
2
1
3
2
4
2
5
0
answer
0
8
1
12
2
6
3
10
4
10
5
10
answer = [8, 12, 6, 10, 10, 10]
algo
master
.
io
Step:
Sum of Distances in Tree: distance sum for every node
0 / 177
Input
Standard
Small
Path
Custom
n
=
6
,
edges
=
[[0,1],[0,2],[2,3],[2,4],[2,5]]
0 / 177
algo
master
.
io
Step:
Sum of Distances in Tree: distance sum for every node
