Show problems as
Classic problem #3558MediumMathTreeDepth-First Search

Number of Ways to Assign Edge Weights I

Real-world version: Odd Weightings on the Longest Branch
Tracked in this browser only
Read Number of Ways to Assign Edge Weights I on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def odd_weightings(edges: list[list[int]]) -> int:
Java
public int oddWeightings(int[][] edges)

More on the same topics