EVENODD1 - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice

Contest

Author: Ayush Kumar

Editorialist: Ayush Kumar

DIFFICULTY:

Easy

PREREQUISITES:

DFS, LCA

PROBLEM:

Given a weighted tree of N vertices, you will be given Q queries containing two nodes (U,V), for each query find the sum of all even length edges or all odd length edges between these pair of nodes if the total sum between these two nodes is odd or even.

EXPLANATION:

For solving the partial problem:O(N^2)

For each query (U,V) do a DFS from U and store the path to V. Now traverse this path and find the sum of odd length edges, even length edges and total sum of edges. Now print the even length sum if total sum is odd or vice-versa.

For solving the complete problem:O(Nlog(N))

Root the tree say (1). Now do a DFS from the root. Now for every node store the sum of even length & odd length edges contained in the path between root to that node. Also, do a precomputation for finding the LCA (Lowest Common Ancestor).

Now for each query (U,V) find the LCA L. Now the answer for the query is even[U] + even[V] - 2 * even[L] or odd[U] + odd[V] - 2 * odd[L] depending on whether total sum is odd or even.

SETTER’S SOLUTION:

Can be found here.

1 Like
2

Can you explain the precomputation of LCA a bit further? I’m having trouble getting testcase #4 within time limits which I suspect is because of the graph geometry.

Edit: So here’s how I updated. After picking a root arbitrarily, each node of the tree retains its power-of-two steps ancestors towards the root - so first ancestor, second ancestor, fourth ancestor, eighth ancestor etc. Then when looking for the last common ancestor of two nodes, the first thing is to move the lower node up to the same level; this can be done in the same number of steps as the 1s in the binary version of the difference in root distance. Then if the nodes are not the same, move up the ancestor tree until they have a common highest ancestor, and then search in binary fashion within that remaining space for the LCA. Python code here

3

Go through these link -

https://cp-algorithms.com/graph/lca_binary_lifting.html

you will get to know much about LCA

1 Like
4

@ayushkmr that worked a treat, thanks.

1 Like