# Given tree with 0 or 1 assigned to each node, count paths with odd number of ones in it

Let's say we have given tree of $$N$$ nodes and $$N-1$$ edges, each of the $$N$$ nodes is assigned one integer, either $$0$$ or $$1$$. We want to count all paths between two nodes $$u$$ and $$v$$ such that on the shortest path from node $$u$$ to node $$v$$ there are odd numbers of ones ( or in other words the sum of all integers on this path is odd number ).

I know that this can be solved easily by running a single DFS from each node, but this works in $$O(N^2)$$. I'm trying to find way to narrow it down to $$O(N\log N)$$ or $$O(N)$$. I was thinking about applying some dynamic programming, but I couldn't find the relations between the nodes.

Scan the tree from the leaves up toward the root, for each vertex $$v$$ calculating, for $$b \in \{0,1\}$$, the number of vertices $$u$$ below $$v$$ such that the $$(v,u)$$ path has the same parity as $$b$$.