We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
It's definitely worth the time to learn about Fenwick trees. These will allow you to add items, remove items, and count a range of items in O(log(n)) time. After that it's fairly straightforward.
This is the approach I took:
- Built the adjacency list from the directed edges.
- Found the root using a math trick: n(n+1)/2 - sum(edges[i][1]).
- Created a FT starting with an array of n nodes of 0.
- DFS through the tree:
-- Count the nodes in the tree between current-k and current+k (truncated to 1..n ).
-- If the current node isn't a leaf:
--- Set the current node.
--- Add the counts from the children.
--- Clear the current node.
Similar Pair
You are viewing a single comment's thread. Return to all comments →
It's definitely worth the time to learn about Fenwick trees. These will allow you to add items, remove items, and count a range of items in O(log(n)) time. After that it's fairly straightforward.
This is the approach I took:
- Built the adjacency list from the directed edges.
- Found the root using a math trick: n(n+1)/2 - sum(edges[i][1]).
- Created a FT starting with an array of n nodes of 0.
- DFS through the tree:
-- Count the nodes in the tree between current-k and current+k (truncated to 1..n ).
-- If the current node isn't a leaf:
--- Set the current node.
--- Add the counts from the children.
--- Clear the current node.