[CodeChef] Starters 80 — c8kbf and Tree: the O(N²) loop that can't run long

Published 4 October 2026

Problem: CodeChef — c8kbf and Tree (Starters 80, difficulty 2001). Official editorial: C8KBFTREE — Editorial.

You’re given a weighted tree with \(N\) vertices. The value of the path from \(x\) to \(y\) is the XOR of its edge weights. Find \(a < b\) and \(c < d\) with \((a, b) \ne (c, d)\) such that the path \(a \to b\) and the path \(c \to d\) have the same value. The four vertices don’t need to be distinct, so \(a = c\) is fine as long as \(b \ne d\). Print \(-1\) if no such pair of pairs exists.

Constraints: \(3 \le N \le 10^5\), \(\sum N \le 3 \cdot 10^5\), \(T \le 10\), \(0 \le w_i \le 2^{20}\).

Observation 1: path XOR is a difference of root XORs

Root the tree at vertex \(1\) and let \(p_v\) be the XOR of the weights on the path from the root to \(v\). For any \(a, b\), the root-to-\(a\) and root-to-\(b\) paths share the part from the root down to their LCA. That shared part appears twice in \(p_a \oplus p_b\), so it cancels:

\[\text{value}(a, b) = p_a \oplus p_b.\]

So the tree disappears after one DFS. The question becomes: among the \(\binom{N}{2}\) values \(p_a \oplus p_b\), are two equal?

Where I started

The obvious method is to enumerate pairs \((a, b)\), store each XOR in a dictionary, and stop at the first repeat. I wrote it off right away: \(\binom{N}{2}\) is about \(5 \cdot 10^9\) for \(N = 10^5\), so I expected it to time out and started looking for something smarter.

Meanwhile my DFS was wrong in two ways:

def dfs(u, p):
    for (v, w) in adj[u]:
        if v == p:
            continue
        dfs(v, u)

    pxor[v] = pxor[u] ^ w   # after the loop: only the last child gets a value

• The assignment sits outside the loop. It runs once, with whatever v, w the loop ended on, so only the last neighbour gets a value. A leaf with only its parent as a neighbour writes into its parent’s entry. It also has to run before dfs(v, u), because the children of v read pxor[v].
• Even when it’s fixed, a path-shaped tree with \(10^5\) vertices recurses \(10^5\) levels deep. sys.setrecursionlimit only raises Python’s limit. The C stack can still overflow. An explicit stack avoids that.

Observation 2: the dictionary fills up first

Every weight is at most \(2^{20}\), so it fits in 21 bits. XOR never sets a bit that none of its inputs has, so every \(p_v\), and every \(p_a \oplus p_b\), lies in \([0, 2^{21})\).

There are only \(2^{21}\) possible values. By the pigeonhole principle, among any \(2^{21} + 1\) pairs two have the same XOR. The enumeration stops at the first repeat, so it runs at most \(2^{21} + 1 \approx 2.1 \cdot 10^6\) iterations, whatever \(N\) is. The \(O(N^2)\) loop is really \(O(\min(N^2, 2^{21}))\). I had the right algorithm and threw it out because I didn’t check how long it could actually run.

The same argument shows when \(-1\) is possible at all. It needs all \(\binom{N}{2}\) values to be distinct, so \(\binom{N}{2} \le 2^{21}\), which means \(N \le 2048\). Every larger tree has an answer.

Correctness is straightforward. The loop only visits pairs with \(a < b\), a dictionary hit pairs the current pair with an earlier one, and pairs are never visited twice, so the two pairs differ. If the loop finishes without a hit, all \(\binom{N}{2}\) values were distinct and \(-1\) is correct.

Code

One iterative DFS in \(O(N)\), then at most \(2^{21} + 1\) dictionary operations per test. In Python, a run of \(2^{21}\) iterations with no repeat takes about 0.5 s on my machine. Real tests stop much sooner: with random weights a repeat turns up after roughly \(\sqrt{2^{21}} \approx 1500\) pairs. Checked against a brute force (explicit path XOR for every pair) on random small trees.

import sys


def solve():
    n = int(input())
    adj = [[] for _ in range(n)]
    for _ in range(n - 1):
        u, v, w = map(int, input().split())
        u -= 1
        v -= 1
        adj[u].append((v, w))
        adj[v].append((u, w))

    # pxor[v] = XOR of the edge weights on the path from vertex 0 to v.
    # Iterative DFS: a path of 10^5 vertices is too deep for Python recursion.
    pxor = [0] * n
    parent = [-1] * n
    stack = [0]
    while stack:
        u = stack.pop()
        for v, w in adj[u]:
            if v == parent[u]:
                continue
            parent[v] = u
            pxor[v] = pxor[u] ^ w
            stack.append(v)

    # Every pair XOR is below 2^21, so this finds a repeat within 2^21 + 1 pairs.
    seen = {}
    for a in range(n):
        for b in range(a + 1, n):
            value = pxor[a] ^ pxor[b]
            if value in seen:
                c, d = seen[value]
                print(a + 1, b + 1, c + 1, d + 1)
                return
            seen[value] = (a, b)

    print(-1)


input = sys.stdin.readline
tc = int(input())
for _ in range(tc):
    solve()

The lesson. Before dismissing a brute force as \(O(N^2)\), check whether it can actually run that long. When the values come from a small range (here 21-bit XORs) and the search stops at the first collision, the pigeonhole principle caps the work at the number of possible values plus one, however large \(N\) gets. A small value range together with a large \(N\) in the constraints is a hint to look for this.