EVENODD2 - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice

Contest

Author: Ayush Kumar

Editorialist: Ayush Kumar

DIFFICULTY:

Hard

PREREQUISITES:

DFS, LCA, HLD

PROBLEM:

Given a weighted tree of N vertices, you will be given Q queries of two types -

  1. 1 U V L modify the existing edge between U & V to length L
  2. 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.

1 Like