0861MediumMathTreeDepth-First Search

Odd Weightings on the Longest Branch

Tracked in this browser only

Trains the technique from

LeetCode 3558Number of Ways to Assign Edge Weights I

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. Junction 1 is the pumping station.

Let m be the greatest number of pipes on any run that starts at the pumping station and never doubles back.

Each of those m pipes is to be given a weight of either 1 or 2. Return how many ways the weights can be chosen so that they add up to an odd total, taken modulo 1000000007.

Examples

Example 1

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

The junctions form a line, so the longest run out of the station holds three pipes. Of the eight weightings of three pipes, four add up to an odd total.

Example 2

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

The longest run holds two pipes. Of the four weightings, the two that use one 1 and one 2 add up to an odd total.

Example 3

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

Every junction hangs directly off the station, so the longest run is one pipe however many branches there are.

Constraints

2 <= edges.length + 1 <= 10^5
edges.length >= 1
edges[i].length == 2
1 <= edges[i][0] <= 100000
1 <= edges[i][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(edges: list[list[int]]) -> int:

Java

public int oddWeightings(int[][] edges)

The intended approach

Time O(n) for n junctions: one walk to measure the longest run, then a fast power.Space O(n) for the neighbour lists and the walk.

Only the length of the longest run matters, not which run it is, so first measure that length with a layer-by-layer walk out from the pumping station, driven by an explicit queue so a long chain cannot exhaust the call stack. A weight of 1 is odd and a weight of 2 is even, so the total is odd exactly when an odd number of the pipes were given a 1. Among all the ways to choose which pipes get a 1, exactly half have an odd count, so the answer is two raised to one less than that length, reduced by the modulus.

Pythonentry point: odd_weightings

def odd_weightings(edges):
    n = len(edges) + 1
    nbr = [[] for _ in range(n + 1)]
    for u, v in edges:
        nbr[u].append(v)
        nbr[v].append(u)
    seen = [False] * (n + 1)
    seen[1] = True
    layer = [1]
    depth = 0
    while layer:
        nxt = []
        for here in layer:
            for step in nbr[here]:
                if not seen[step]:
                    seen[step] = True
                    nxt.append(step)
        if nxt:
            depth += 1
        layer = nxt
    if depth == 0:
        return 0
    return pow(2, depth - 1, 1000000007)

The obvious version

Measure the longest run with an explicit stack that carries each junction's distance from the station, then build that run one pipe at a time, tracking how many weightings so far give an odd total and how many give an even one. Accumulates the count step by step instead of using any 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(edges):
    n = len(edges) + 1
    nbr = [[] for _ in range(n + 1)]
    for u, v in edges:
        nbr[u].append(v)
        nbr[v].append(u)
    best = 0
    stack = [(1, 0, 0)]
    while stack:
        here, came, dist = stack.pop()
        if dist > best:
            best = dist
        for step in nbr[here]:
            if step != came:
                stack.append((step, here, dist + 1))
    if best == 0:
        return 0
    # build the run one pipe at a time, tracking how many weightings so far give
    # an odd total and how many give an even one
    odd = 0
    even = 1
    for _ in range(best):
        odd, even = (even + odd) % 1000000007, (odd + even) % 1000000007
    return odd

How this problem was checked

Reference solution executed against 12 test cases — 12 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