Tap here to switch tabs
Problem
Submissions

Problem: Minimum Edge Weight Equilibrium Queries in a Tree

Minimum Edge Weight Equilibrium Queries in a Tree asks for each node pair how many path-edge weights must change so every edge on that path has the same weight. Queries are independent.

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

Minimum Edge Weight Equilibrium Queries in a Tree asks for each node pair how many path-edge weights must change so every edge on that path has the same weight. Queries are independent.

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