Contest: ICO 2018 Practice Contest 1
Practice: Practice Link
Author: Shashwat Goel
Tester: Udit Sanghi
Editorialist: Shashwat Goel
Problem Statement
Given a graph with N vertices and N-1 edges and Q queries, you have to find the parity of path length from a node A to node B for each query.
Explanation
Theorem: Any connected graph with N vertices and N−1 edges is a tree. Proof Let G be a connected graph with N vertices and N − 1 edges. We show that G contains no cycles. Assume to the contrary that G contains cycles. Remove an edge from a cycle so that the resulting graph is again connected. Continue this process of removing one edge from one cycle at a time till the resulting graph H is a tree. As H has N vertices, so number of edges in H is N−1. Now, the number of edges in G is greater than the number of edges in H. So N−1 > N−1, which is not possible. Hence, G has no cycles and therefore is a tree.
Therefore the given graph is a tree (note that the above proof is a basic property of a tree and questions like these assume you know this).
Now, since it’s a tree, the shortest path between 2 nodes can be calculated by dfs/bfs. This gives you an O(NQ) solution, which solves the first subtask.
Now moving for the second subtask, one must notice that the distance between 2 nodes of a tree is given by
(FORMULA 1):
This is evident if you draw some trees. The depth is the distance of a node from the root.
In this question, we can fix any node as the root (because the tree is bidirectional, if you change the root the orientation of the tree changes but everything else remains the same). So we fix a root and pre compute the LCA of all pairs of vertices (in O(N) or O(LogN)). Then we can answer the Queries in O(1) by checking the parity of Formula 1. This solution takes O(N^2) time for precomputation and O(1) for the queries. It therefore works on Subtask 2. This however doesnt work for subtask 1.Now notice that subtask 1 and 2 are exclusive, one has a low number of nodes and high number of queries while the other has a high number of nodes and low number of queries. So we use them exclusively in our code, that is check if N>10^3, then do the first method otherwise second.
Now, there is an algorithm for computing the LCA: Link
Now if you can code the O(LogN) computation in the above link, You can simply find the LCA for every query without having to precompute anything. This solution works for all of the above, subtask 1 2 and 3.
But here is the fun part. The actual solution is much easier, and does not require computation of the LCA in this particular problem. There is just one clever observation:
Notice formula 1 again.
Notice that 2*D[LCA] is always even. Also notice that when an even number is subtracted/added from a number, it does not change the numbers parity, i.e. Odd±Even = Odd and Even± Even=Even. So we can eliminate this term. THUS, the answer is independent of the LCA and WE DO NOT NEED TO COMPUTE IT!
You simply find the parity of D + D[V] and you’re done!
So conclusion: The final algorithm requires a single DFS precomputation to compute the depth of each node. Then taken the queries and just check if D+D[V] is odd or even and output it.
Tester Solution: here
I wikified all others.