Find Paths Going Through a Centroid that Contain the Same Number of A and B Nodes

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?

//