0

We have a graph with N nodes and N-1 bidirectional edges(each edge has some weight w). Now we have to answer q number of queries. Each query gives two nodes u and v and maximum allowed cost at any edge x. If the individual edge weights of all edges between path from u to v is less than or equal to x, then we print Yes otherwise we print No.

The constraints are as follows:
1 ≤ N,q ≤ 10^6
1 ≤ w,x ≤ 10^9

I have tried the brute force solution but it gives TLE. I know I have to do some preprocessing but can't get my head over it. I found a similar question here but no one clearly addressed that part.
Maximum edge weight from one node A to node B.
You can visit the link for better explanation of the problem.

prakasht
  • 448
  • 4
  • 16
  • You can solve this with *Dijkstra's algorithm*, since each node has at most one edge, this will result in an *O(n)* algorithm here. While performing Dijkstra's algorithm, you can "optimize" the graph meanwhile, such that work done in the first query, can be exploited in the second. – Willem Van Onsem Jun 16 '19 at 15:02
  • Please explain that optimisation in an answer. I'm too naive to understand as my knowledge is limited to standard Dijkstra algorithm only. – prakasht Jun 16 '19 at 15:10
  • this *is* the standard Dijkstra algorithm. – Willem Van Onsem Jun 16 '19 at 15:12
  • I don't understand how I can optimize the graph to exploit in further query. Please at least provide the pseudocode or some explanation. – prakasht Jun 16 '19 at 15:21
  • I'm voting to close this question as off-topic because this is a question about computer science, not programming. – Daniel Mann Jun 16 '19 at 15:27
  • @DanielMann This question was asked in a 2 hour programming contest. – prakasht Jun 16 '19 at 15:39

1 Answers1

3

This can be easilly solved using Union Find (also known as Diesjoint Set Union, if never heard about it you can look up implementation here) data structure in O(nlog(n) + qlog(q))

  1. Read all queries and store them in some array structure (keeping query info u v x and index of query)

  2. Sort all queries by weight

  3. Sort all edges by weight

  4. Go throught all queries, if needed merge all still unmerged edges with weight <= query weight

  5. If nodes u and v are in same connected component (Find(u)==Find(v)) then answer for this querie is Yes else no

  6. Print answers in needed order
Photon
  • 2,717
  • 1
  • 18
  • 22