Author: Ayush Kumar
Editorialist: Ayush Kumar
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.
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 + even[V] - 2 * even[L] or odd + odd[V] - 2 * odd[L] depending on whether total sum is odd or even.
Can be found here.