Problem: http://www.usaco.org/index.php?page=viewproblem2&cpid=195

In order to apply centroid decomposition to this problem, I need to find all paths that go through a centroid node *N* and have the same number of ‘(’ and ‘)’ nodes. How can I do this in *O(N)* time?