Tap here to switch tabs
Problem
Submissions

Problem: Minimum Edge Weight Equilibrium Queries in a Tree

Try to solve the Minimum Edge Weight Equilibrium Queries in a Tree problem.

Statement

There is an undirected, weighted tree with nn nodes labeled from 00 to n−1n - 1. The tree is represented by a 22D integer array edges of length n−1n - 1, where edges[i] = [ui,vi,wi][u_i, v_i, w_i] indicates that there is an edge between nodes uiu_i and viv_i with weight wiw_i.

You are also given a 22D integer array queries of length mm, where queries[i] = [ai,bi][a_i, b_i].

For each query, determine the minimum number of operations needed to make the weights of all edges on the path between nodes aia_i and bib_i equal. In one operation, you can choose any edge in the tree and change its weight to any positive integer.

Return an array answer of length mm, where answer[i] is the answer to the iextthi^{ ext{th}} query.

Note: Each query is independent. Changing edge weights for one query does not affect the tree for other queries.

Constraints:

  • 1≤1 \leq n ≤104\leq 10^4

  • edges.length =n−1= n - 1

  • edges[i].length =3= 3

  • 0≤ui,vi<0 \leq u_i, v_i < n

  • 1≤wi≤261 \leq w_i \leq 26

  • The input is generated such that edges represents a valid tree.

  • 1≤1 \leq queries.length =m≤2imes104= m \leq 2 imes 10^4

  • queries[i].length =2= 2

  • 0≤ai,bi<0 \leq a_i, b_i < n

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Minimum Edge Weight Equilibrium Queries in a Tree

Try to solve the Minimum Edge Weight Equilibrium Queries in a Tree problem.

Statement

There is an undirected, weighted tree with nn nodes labeled from 00 to n−1n - 1. The tree is represented by a 22D integer array edges of length n−1n - 1, where edges[i] = [ui,vi,wi][u_i, v_i, w_i] indicates that there is an edge between nodes uiu_i and viv_i with weight wiw_i.

You are also given a 22D integer array queries of length mm, where queries[i] = [ai,bi][a_i, b_i].

For each query, determine the minimum number of operations needed to make the weights of all edges on the path between nodes aia_i and bib_i equal. In one operation, you can choose any edge in the tree and change its weight to any positive integer.

Return an array answer of length mm, where answer[i] is the answer to the iextthi^{ ext{th}} query.

Note: Each query is independent. Changing edge weights for one query does not affect the tree for other queries.

Constraints:

  • 1≤1 \leq n ≤104\leq 10^4

  • edges.length =n−1= n - 1

  • edges[i].length =3= 3

  • 0≤ui,vi<0 \leq u_i, v_i < n

  • 1≤wi≤261 \leq w_i \leq 26

  • The input is generated such that edges represents a valid tree.

  • 1≤1 \leq queries.length =m≤2imes104= m \leq 2 imes 10^4

  • queries[i].length =2= 2

  • 0≤ai,bi<0 \leq a_i, b_i < n