Back to problems

Count Pythagorean Distance Triples in a Tree

Algorithm · IBM · Medium

You are given a tree with N nodes numbered from 1 to N and with all edges having unit weight. Three pivot nodes x, y, and z (not necessarily distinct) are also given. For an arbitrary node v of the tree, let $$d(v, x), \quad d(v, y), \quad d(v, z)$$ be the shortest‑path distances from v to the three pivots (each distance is the number of edges on the unique simple path between the two nodes). Sort the three distances in non‑decreasing order and denote them by $$a \le b \le…

Checking your access…