PROBLEM LINK:
Author: Ayush Kumar
Editorialist: Ayush Kumar
DIFFICULTY:
Hard
PREREQUISITES:
PROBLEM:
Given a weighted tree of N vertices, you will be given Q queries of two types -
- 1 U V L modify the existing edge between U & V to length L
- 2 U V 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:
Form the HLD of the tree. Now updating the edge can be done in log(N) time. Also, each query is solved in log(N) * log(N).
SETTER’S SOLUTION:
Can be found here.