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.