Show problems as
Classic problem #3559HardArrayMathDynamic ProgrammingBit ManipulationTreeDepth-First Search

Number of Ways to Assign Edge Weights II

Real-world version: Odd Weightings on Many Runs
Tracked in this browser only
Read Number of Ways to Assign Edge Weights II 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.

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 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_per_run(edges: list[list[int]], queries: list[list[int]]) -> list[int]:
Java
public List<Integer> oddWeightingsPerRun(int[][] edges, int[][] queries)

More on the same topics