n nodes numbered 0 to n - 1. Its edges are given in links of length n - 1: a pair [a, b] is an edge between nodes a and b. Which node is the root is unknown.
Someone has made claims about the tree in claims: a pair [u, v] means "u is the parent of v", and u and v are always joined by an edge. All that is known is that at least need of these claims are true.
Return the number of nodes that could be the root, meaning that when the tree hangs from that node, at least need claims hold.links=[[0, 1], [1, 2], [1, 3]], claims=[[1, 0], [1, 2], [3, 1]], need=2 → 2
Root 0: only "1 is the parent of 2" holds. Root 1: "1 is the parent of 0" and "1 is the parent of 2" hold. Root 2: only "1 is the parent of 0" holds. Root 3: all three hold. Roots 1 and 3 qualify.
links=[[0, 1]], claims=[[0, 1]], need=0 → 2
With need = 0 any root works, so the answer is 2.
links=[[2, 0], [0, 1]], claims=[[0, 1], [1, 0]], need=2 → 0
"0 is the parent of 1" and "1 is the parent of 0" can never both be true, so no root qualifies.
[u, v] is an edge of the tree, and no claim repeatslinks=[[0, 1], [1, 2], [1, 3]], claims=[[1, 0], [1, 2], [3, 1]], need=2
2
Run checks the first 3 tests in your browser. Submit checks all 63 tests on the server, hidden ones included.