algorithm - Counting Zero-Sum Paths in a Tree -

we given tree n (up 100,000) nodes. each edge weighted either +1 or -1 , nodes numbered 1 n. how many unordered pairs (a, b) exist such on path a -> x -> b, x (x != && x != b) vertex on path between a , b, sum of edge weights on path a -> x 0 , sum of edge weights on path x -> b 0?

it follows care path lengths, or else sum of edge weights cannot 0. cannot iterate on potential a , b, or else o(n^2) solution, not run under 1 second. tips on how solve it? program should run under 1 second, o(n) or o(n logn) solution work.

edit: however, if can calculate number of paths starting each node, able solve problem. possible calculate this? sounds dp-ish me, i'm not sure.

i'm going develop algorithm below starts off o(n^2). small observation can change complexity substantially smaller. i'm not quite sure (o(n) or o(nlnn)), seems less o(n^2).

1. in tree, choose arbitrary leaf node x0, , create empty list l0.
2. follow leaf node 1 branch. if list non-empty add value of edge weight each term of list, records cumulative sum of edge weights far.
3. append edge weight list.
4. if new node has 2 branches, goto step 2 traveling new direction , updating l0. repeat until there 3 or more branches on new node.
5. for each branch (other direction came from) recursively start on each sub-tree step 1, except in sub-tree mark node special. when recursion reachs node merge (step 5) , halt.
6. merging: have set of lists l0, l1, l2, ... must merged l0. each of these lists represent different paths , respective cumulative sums. each pair in each list, add counter, m number of times these sums equal zero. this associates sum each possible path in graph. create new list l0 concatenation of set l0, l1, l2, ....

the algorithm above works, since performing sum each graph path, cost must @ least o(n^2).

the trick here not count every path. if instead, sort lists, determining if 2 sorted lists of size k1,k2 have fixed sum c can done iterating through lists, 1 forward 1 backwards. counting can done each pair of lists in k1+k2 operations not k1*k2 operations before. merging lists trivial , has same complexity since sorted.

bonus: above method trivially extends arbitrary edge weights (not -1, 1) , arbitrary fixed sum (not zero).