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.
You can solve in linear time this using dynamic programming on trees.

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$.