how to approch this problem can any one help please
constrain 2<=N,Q<=10^5
Constraints?
2<=N,Q<=10^5
You can sort both queries and edges w.r.t to weights and apply dsu for maintaining each connected component. For each query you can check whether the two belongs to same connected component or not.
2 Likes
can u explain a bit pls… and what will be the time complexity… thanks for help
Pretty sure discussing on-going contests isn’t allowed.
this is not an ongoing contest
I see. Thanks for clarifying.
wow you got easy one
Bro from where did you get the challenge id? I received no email. Did you do any registration to get the email?
can anyone tell me how to know when google helds contests?
Well, first build a minimum spanning tree of the graph and then use binary lifting on tree to answer the queries.
Note that minimum spanning tree minimizes the maximum edge of any path between 2 nodes in a graph. The problem is known as the Minimax Path problem.
Complexity : O(N*log(N) + Q*log(N))
2 Likes