All Tracks Data Structures Trees Binary Search Tree Problem

MST revisited
Tag(s):

Hard, hard

Problem
Editorial
Analytics

Given an undirected graph of N nodes and N weighted edges, it doesn't contain parallel edges nor self loops, it's guaranteed the graph will always remain connected.

you have to support Q queries, in each query you will be given one edge to delete and one edge to add in such a way to graph will remain connected, after each query you have to tell the cost of minimum spanning tree.

you have to provide an online solution (i.e. you can't see future queries until you answer the current one)

Input:

First line contains two integers N and Q.

Each of the next N lines describe an edge by 3 integers u, v, c, it means there's an edge connecting nodes u and v and has weight equal to c.

Each of the next Q lines describe a query by 5 integers x1, x2, x3, x4, x5, let ans be the answer to previous query (if this is first query then ans = 0). now let a = x1 + (ans mod 100), b = x2 + (ans mod 100), u = x3 + (ans mod 100), v = x4 + (ans mod 100), c = x5 + (ans mod 100), it means to delete edge connecting nodes a and b and add edge connecting u and v and has weight equal to c.

Output:

Output the answer to each query in new line, the answer is one integer equal to sum of weights of minimum spanning tree of the graph.

Constraints:

  • 3 <= N <= 300,000
  • 1 <= Q <= 300,000
  • Graph will always remain connected without self loops nor parallel edges
  • 1 <= weight of edges <= 1,000,000
SAMPLE INPUT
6 2
1 2 2
1 3 3
1 4 4
1 5 5
1 6 6
5 6 7
5 6 2 3 7
-18 -17 -17 -16 -13
SAMPLE OUTPUT
20
20
Explanation

after the first query the minimum spanning tree will consist of all edges except edge (2,3), so answer is 20. now the second query is 2 3 3 4 7 (we added 20 to all 5 numbers).

and again after the second query the minimum spanning tree is the same and the answer is 20.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

July Circuits '17

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications