1
$\begingroup$

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.

|cite|improve this question
$\endgroup$
2
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I have implemented dp on trees but, the standard way from root to leaves, how can we implement it the other way $\endgroup$ – someone12321 Nov 18 '18 at 6:51
  • $\begingroup$ The standard way is leaves to root. We probably refer to the same thing, only call it by different names. $\endgroup$ – Yuval Filmus Nov 18 '18 at 8:33
  • $\begingroup$ Yes probably, but in such way we are only counting paths that start in node x and finish in node y which is in subtree of node x, however there might be paths that start in this node go upper in the tree and then continue in some other subtree, how are we counting those paths $\endgroup$ – someone12321 Nov 18 '18 at 9:34
  • $\begingroup$ It’s enough to count paths that go down. If a path goes up, then looking at it from the other end, it goes down. $\endgroup$ – Yuval Filmus Nov 18 '18 at 17:06
  • $\begingroup$ Yes, but some paths go up then they go down at other node, how is that counted, if we root the tree at node 1 $\endgroup$ – someone12321 Nov 18 '18 at 17:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.