Modified Union-Find with Weighted Graph Components

Problem Statement

You are given n nodes and a list of edges where each edge has a weight. Two nodes are in the same component if they are connected.

Design a data structure that supports:

1. union(u, v, weight) — Merge the components containing u and v. The weight represents the ratio relationship value[u] / value[v] = weight.
2. query(u, v) — If u and v are in the same component, return the ratio value[u] / value[v]. Otherwise return -1.0.

This is essentially a weighted Union-Find where edges store multiplicative relationships between nodes.

Constraints

• 1 <= n <= 10^5
• 1 <= edges.length <= 2 * 10^5
• 0.0 < weight <= 100.0
• Queries can be interleaved with union operations

Example

union(0, 1, 2.0)   // value[0] / value[1] = 2.0
union(1, 2, 3.0)   // value[1] / value[2] = 3.0

query(0, 2)  → 6.0   // value[0]/value[2] = (value[0]/value[1]) * (value[1]/value[2]) = 2*3 = 6
query(2, 0)  → 0.167 // value[2]/value[0] = 1/6
query(0, 3)  → -1.0  // not connected

Follow-ups

1. How do you handle path compression while maintaining correct weight calculations?
2. What happens when a union creates a contradiction (conflicting ratio)? How would you detect it?
3. Can you support a delete(u, v) operation? What are the challenges?
4. What's the amortized time complexity with both path compression and union by rank?