0862HardArrayMathDynamic ProgrammingBit ManipulationTreeDepth-First Search

Odd Weightings on Many Runs

Tracked in this browser only

Trains the technique from

LeetCode 3559Number of Ways to Assign Edge Weights II

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A pipe network is a tree of n junctions numbered 1 through n, joined by n - 1 pipes given as edges, where edges[i] = [u, v] is a pipe between junction u and junction v.

Each query queries[j] = [u, v] names two junctions. Exactly one run of pipes joins them without doubling back; let m be how many pipes that run holds.

Each of those m pipes is to be given a weight of either 1 or 2. For each query return how many ways the weights can be chosen so that they add up to an odd total, taken modulo 1000000007. When the two junctions are the same the run holds no pipes, and no choice of weights can make an odd total, so the answer is 0.

Examples

Example 1

Input: edges = [[1, 2], [2, 3], [1, 4]], queries = [[3, 4], [1, 1], [2, 4]]
Output: [4, 0, 2]

The run from junction 3 to junction 4 holds three pipes, so four of its eight weightings total odd. The second query names the same junction twice, so its run holds no pipes. The third holds two pipes.

Example 2

Input: edges = [[1, 2], [1, 3], [1, 4]], queries = [[2, 3], [2, 4], [3, 4]]
Output: [2, 2, 2]

Every junction hangs directly off junction 1, so each of these runs holds two pipes and two of the four weightings total odd.

Example 3

Input: edges = [[1, 3], [3, 2]], queries = [[1, 2]]
Output: [2]

The run from junction 1 to junction 2 goes by way of junction 3 and holds two pipes.

Constraints

2 <= edges.length + 1 <= 10^5
edges.length >= 1
edges[i].length == 2
1 <= edges[i][0] <= 100000
1 <= edges[i][1] <= 100000
1 <= queries.length <= 10^5
queries[j].length == 2
1 <= queries[j][0] <= 100000
1 <= queries[j][1] <= 100000
edges describes a tree on the junctions 1 through edges.length + 1

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def odd_weightings_per_run(edges: list[list[int]], queries: list[list[int]]) -> list[int]:

Java

public List<Integer> oddWeightingsPerRun(int[][] edges, int[][] queries)

The intended approach

Time O(n log n) to prepare the ancestor tables, then O(log n) per query.Space O(n log n) for the ancestor tables.

A weight of 1 is odd and a weight of 2 is even, so a run's total is odd exactly when an odd number of its pipes were given a 1. Among the ways to choose which pipes get a 1, exactly half have an odd count, so a run of `m` pipes has two raised to `m - 1` odd weightings, and a run of no pipes has none. So each query only needs the length of its run. Root the tree at junction 1 with a layer-by-layer walk driven by an explicit queue, recording each junction's depth and its ancestors at power-of-two heights. The run between two junctions holds their depths added together minus twice the depth of their deepest shared ancestor, which those ancestor tables find by lifting the deeper junction level with the shallower and then climbing both together.

Pythonentry point: odd_weightings_per_run

def odd_weightings_per_run(edges, queries):
    MOD = 10 ** 9 + 7
    n = len(edges) + 1
    nbr = [[] for _ in range(n + 1)]
    for u, v in edges:
        nbr[u].append(v)
        nbr[v].append(u)

    depth = [0] * (n + 1)
    up = [[0] * (n + 1)]
    seen = [False] * (n + 1)
    seen[1] = True
    order = [1]
    head = 0
    while head < len(order):
        here = order[head]
        head += 1
        for step in nbr[here]:
            if not seen[step]:
                seen[step] = True
                depth[step] = depth[here] + 1
                up[0][step] = here
                order.append(step)
    up[0][1] = 1

    levels = 1
    while (1 << levels) < n:
        levels += 1
    for k in range(1, levels + 1):
        row = [0] * (n + 1)
        for node in range(1, n + 1):
            row[node] = up[k - 1][up[k - 1][node]]
        up.append(row)

    def shared(a, b):
        if depth[a] < depth[b]:
            a, b = b, a
        gap = depth[a] - depth[b]
        k = 0
        while gap:
            if gap & 1:
                a = up[k][a]
            gap >>= 1
            k += 1
        if a == b:
            return a
        for k in range(len(up) - 1, -1, -1):
            if up[k][a] != up[k][b]:
                a = up[k][a]
                b = up[k][b]
        return up[0][a]

    out = []
    for u, v in queries:
        m = depth[u] + depth[v] - 2 * depth[shared(u, v)]
        out.append(0 if m == 0 else pow(2, m - 1, MOD))
    return out

The obvious version

For each query, walk the tree outward from one junction until the other is reached, counting the pipes on the way, then build up the count of odd-total weightings one pipe at a time. Repeats the walk for every query and uses no ancestor tables or closed form.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_odd_weightings_per_run(edges, queries):
    MOD = 10 ** 9 + 7
    n = len(edges) + 1
    nbr = [[] for _ in range(n + 1)]
    for u, v in edges:
        nbr[u].append(v)
        nbr[v].append(u)
    out = []
    for u, v in queries:
        dist = 0
        if u != v:
            seen = [False] * (n + 1)
            seen[u] = True
            layer = [u]
            found = False
            while layer and not found:
                dist += 1
                nxt = []
                for here in layer:
                    for step in nbr[here]:
                        if not seen[step]:
                            if step == v:
                                found = True
                                break
                            seen[step] = True
                            nxt.append(step)
                    if found:
                        break
                layer = nxt
        if dist == 0:
            out.append(0)
            continue
        odd = 0
        even = 1
        for _ in range(dist):
            odd, even = (even + odd) % MOD, (odd + even) % MOD
        out.append(odd)
    return out

How this problem was checked

Reference solution executed against 10 test cases — 10 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in