RAJAPR0 - Editorial

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):

\text{Depth of starting node} + \text{Depth of Final node} - 2 \times \text{Depth of Lowest Common Ancestor}

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.

\text{Length of Path}=D[U]+D[V]-2*D[LCA]

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[U] + 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[U]+D[V] is odd or even and output it.

Tester Solution: here

2 Likes

I did it in easier way.dfs of node.colored by 0 and 1.if xor value of two node is 1 then odd otherwise even
(By observation).My code got AC.tell me if i’m wrong!! @ista @mathecodician

solution

where is practice section link???//

Can’t we find the depth of each node by one bfs precomputation instead of dfs ?

@ista2000 , please wikify it yourself. Server glitches are a pain -_-

You did the same thing. We are storing the distances and finding the parity of their sum, you are storing parity and xoring; both are equivalent. Also, Both solutions are one pass dfs preprocessing.

@vijju123 Sorry I forgot :stuck_out_tongue: I wikified all others.

I wikified it twice ;_; Doesn’t work

Even @admin faced the problem I guess. If she couldn’t do it, who are we :3

1 Like

You just go to the contest link, then to the problem page and remove the contest code from the URL. :confused:

He meant “if contest link is given, then why not practice link which is more relevant”

Because when I posted the editorial, that time the practice link was not live :3

we can do the same, bfs or dfs doesnt matters much here, both works fine!