Hello! I have come across a tree problem where number of nodes(V<=1e5) and number of edges(E<=1e5) and edge weights are given .There are Q (Q<=1e5) queries of two types:
Query 1 asks to change the weight of edge i to W (given in query) Query 2 asks to print the path length between nodes a and b (given in query)
//As I know, LCA can be used to find the distance when edge weights are not changing (But does not seem to be useful here)
Can anyone suggest any method on how to solve it efficiently ?
Using heavy-light decomposition should be ok
Thanks man! Got the ROOT.
Instead of doing HLD, you can do Euler Tour Tree+fenwick, which will work faster and will be much easier to write
sqrt decomposition (keep lazy updates and rebuild distance after each B queries)