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?