1020. How Much Taller, If You Can Tell

There are n people whose heights are unknown. You are given m statements, each of the form

a b d person a is exactly d units taller than person b

where d may be negative, meaning a is shorter. All the statements can hold at once.

Then q questions arrive, each naming two people x and y. Print the height of x minus the height of y, or the word UNKNOWN if the statements do not decide it.

``` 4 people, statements (1 2 5) (2 3 -3)

1 and 3 -> 2 5 + (-3) 3 and 1 -> -2 1 and 4 -> UNKNOWN nothing connects person 4 to anybody ```

3 people, statement (1 2 10) 4 people, no statements 2 and 1 -> -10 1 and 2 -> UNKNOWN 1 and 1 -> 0

A person compared with themselves always answers 0, even with no statement mentioning them.

## What most people try first

Build a graph with a signed weight on each edge and walk it from x looking for y, accumulating as you go. That is correct and costs O(n + m) per question, so O(q(n + m)) in total, about 2 * 10^10 at the limits.

## Carry the difference against the PARENT

A plain disjoint set records only which group an element is in. Add one number per element:

> offset[x] is the height of x minus the height of its PARENT

Then the height of x minus the height of its ROOT is the sum of the offsets along the way up, and two people in the same group can be compared by subtracting their two root-relative values. That is the whole idea, and it is what makes this a different structure rather than the same one used differently.

find(x): if parent[x] == x: return (x, 0) (r, off) = find(parent[x]) parent[x] = r offset[x] = offset[x] + off now measured against the root return (r, offset[x])

Path compression has to update the offset at the same moment it rewrites the pointer, or the number becomes a difference against an ancestor that is no longer the parent.

## Merging two groups

Given a is d taller than b, with (ra, oa) and (rb, ob) from the two finds:

if ra != rb: parent[ra] = rb offset[ra] = ob + d - oa

Read that off the definition. We need height(ra) - height(rb). We know height(a) - height(ra) = oa, height(b) - height(rb) = ob and height(a) - height(b) = d. Subtracting the first from the third and adding the second gives exactly ob + d - oa.

## Answering

(rx, ox) = find(x); (ry, oy) = find(y) if rx != ry: print UNKNOWN else: print ox - oy

because both offsets are measured against the same root, so the root cancels.

## The compression that silently corrupts

Rewriting parent[x] to the root WITHOUT adding the parent's offset into offset[x] leaves offset[x] measuring against a node that is no longer above it. Every later answer through x is then wrong by however far that node sat from the root, and the errors only show on inputs deep enough for compression to fire, which small tests do not have. The two-level recursion above adds the two numbers in the one place that is safe.

## Overflow, and it is not optional

Each d fits in a signed 32 bit integer, whose maximum is 2147483647. The ANSWER does not: a chain of three statements of 10^9 each gives 3 * 10^9, and the test for that is in the set. A 32 bit accumulator prints -1294967296 instead. At the full limits a chain of 10^5 statements reaches 10^14, so both offset and the printed value must be 64 bit.

## Cross-reference

Problem 988 records only that two things are EQUAL, which is a difference of exactly zero, so it needs no offsets at all. This is the same structure with the relation carrying a value, and problem 1022 is the same idea again with the value being one bit.

## Cost

Time O((n + m + q) alpha(n)). Space O(n).

Constraints - `1 ≤ n ≤ 100000` - `0 ≤ m ≤ 200000` - `1 ≤ q ≤ 100000` - `1 ≤ a, b, x, y ≤ n` - `-1000000000 ≤ d ≤ 1000000000` - The statements can all hold at once.