3559. Number of Ways to Assign Edge Weights II LeetCode Solution
In this guide, you will get 3559. Number of Ways to Assign Edge Weights II LeetCode Solution with the best time and space complexity. The solution to Number of Ways to Assign Edge Weights II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Number of Ways to Assign Edge Weights II solution in C++
- Number of Ways to Assign Edge Weights II solution in Java
- Number of Ways to Assign Edge Weights II solution in Python
- Additional Resources
Problem Statement of Number of Ways to Assign Edge Weights II
There is an undirected tree with n nodes labeled from 1 to n, rooted at node 1. The tree is represented by a 2D integer array edges of length n – 1, where edges[i] = [ui, vi] indicates that there is an edge between nodes ui and vi.
Initially, all edges have a weight of 0. You must assign each edge a weight of either 1 or 2.
The cost of a path between any two nodes u and v is the total weight of all edges in the path connecting them.
You are given a 2D integer array queries. For each queries[i] = [ui, vi], determine the number of ways to assign weights to edges in the path such that the cost of the path between ui and vi is odd.
Return an array answer, where answer[i] is the number of valid assignments for queries[i].
Since the answer may be large, apply modulo 109 + 7 to each answer[i].
Note: For each query, disregard all edges not in the path between node ui and vi.
Example 1:
Input: edges = [[1,2]], queries = [[1,1],[1,2]]
Output: [0,1]
Explanation:
Query [1,1]: The path from Node 1 to itself consists of no edges, so the cost is 0. Thus, the number of valid assignments is 0.
Query [1,2]: The path from Node 1 to Node 2 consists of one edge (1 → 2). Assigning weight 1 makes the cost odd, while 2 makes it even. Thus, the number of valid assignments is 1.
Example 2:
Input: edges = [[1,2],[1,3],[3,4],[3,5]], queries = [[1,4],[3,4],[2,5]]
Output: [2,1,4]
Explanation:
Query [1,4]: The path from Node 1 to Node 4 consists of two edges (1 → 3 and 3 → 4). Assigning weights (1,2) or (2,1) results in an odd cost. Thus, the number of valid assignments is 2.
Query [3,4]: The path from Node 3 to Node 4 consists of one edge (3 → 4). Assigning weight 1 makes the cost odd, while 2 makes it even. Thus, the number of valid assignments is 1.
Query [2,5]: The path from Node 2 to Node 5 consists of three edges (2 → 1, 1 → 3, and 3 → 5). Assigning (1,2,2), (2,1,2), (2,2,1), or (1,1,1) makes the cost odd. Thus, the number of valid assignments is 4.
Constraints:
2 <= n <= 105
edges.length == n – 1
edges[i] == [ui, vi]
1 <= queries.length <= 105
queries[i] == [ui, vi]
1 <= ui, vi <= n
edges represents a valid tree.
Complexity Analysis
- Time Complexity: O(n\log n + q\log n)
- Space Complexity: O(n + q)
3559. Number of Ways to Assign Edge Weights II LeetCode Solution in C++
class Solution {
public:
vector<int> assignEdgeWeights(vector<vector<int>>& edges,
vector<vector<int>>& queries) {
const int n = edges.size() + 1;
vector<int> ans;
vector<int> depth(n + 1);
vector<vector<int>> graph(n + 1);
vector<vector<int>> parent(kLog, vector<int>(n + 1, -1));
for (const vector<int>& edge : edges) {
const int u = edge[0];
const int v = edge[1];
graph[u].push_back(v);
graph[v].push_back(u);
}
dfs(1, -1, graph, parent, depth);
for (int k = 1; k < kLog; ++k)
for (int v = 1; v <= n; ++v)
if (parent[k - 1][v] != -1)
parent[k][v] = parent[k - 1][parent[k - 1][v]];
for (const vector<int>& query : queries) {
const int u = query[0];
const int v = query[1];
if (u == v) {
ans.push_back(0);
} else {
const int a = lca(u, v, parent, depth);
const int d = depth[u] + depth[v] - 2 * depth[a];
ans.push_back(modPow(2, d - 1));
}
}
return ans;
}
private:
static constexpr int kMod = 1'000'000'007;
static constexpr int kLog = 17; // since 2^17 > 1e5
void dfs(int u, int p, const vector<vector<int>>& graph,
vector<vector<int>>& parent, vector<int>& depth) {
parent[0][u] = p;
for (const int v : graph[u])
if (v != p) {
depth[v] = depth[u] + 1;
dfs(v, u, graph, parent, depth);
}
}
int lca(int u, int v, const vector<vector<int>>& parent,
const vector<int>& depth) {
if (depth[u] < depth[v])
swap(u, v);
for (int k = kLog - 1; k >= 0; --k)
if (parent[k][u] != -1 && depth[parent[k][u]] >= depth[v])
u = parent[k][u];
if (u == v)
return u;
for (int k = kLog - 1; k >= 0; --k)
if (parent[k][u] != -1 && parent[k][u] != parent[k][v]) {
u = parent[k][u];
v = parent[k][v];
}
return parent[0][u];
}
long modPow(long x, long n) {
if (n == 0)
return 1;
if (n % 2 == 1)
return x * modPow(x % kMod, (n - 1)) % kMod;
return modPow(x * x % kMod, (n / 2)) % kMod;
}
};
/* code provided by PROGIEZ */3559. Number of Ways to Assign Edge Weights II LeetCode Solution in Java
class Solution {
public int[] assignEdgeWeights(int[][] edges, int[][] queries) {
final int n = edges.length + 1;
int[] ans = new int[queries.length];
final int[] depth = new int[n + 1];
final int[][] parent = new int[LOG][n + 1];
List<Integer>[] graph = new List[n + 1];
Arrays.setAll(graph, i -> new ArrayList<>());
for (int[] edge : edges) {
final int u = edge[0];
final int v = edge[1];
graph[u].add(v);
graph[v].add(u);
}
dfs(1, -1, graph, parent, depth);
for (int k = 1; k < LOG; ++k)
for (int v = 1; v <= n; ++v)
if (parent[k - 1][v] != -1)
parent[k][v] = parent[k - 1][parent[k - 1][v]];
for (int i = 0; i < queries.length; ++i) {
final int u = queries[i][0];
final int v = queries[i][1];
if (u == v) {
ans[i] = 0;
} else {
final int a = lca(u, v, parent, depth);
final int d = depth[u] + depth[v] - 2 * depth[a];
ans[i] = modPow(2, d - 1);
}
}
return ans;
}
private static final int MOD = 1_000_000_007;
private static final int LOG = 17; // since 2^17 > 1e5
private void dfs(int u, int p, java.util.List<Integer>[] graph, int[][] parent, int[] depth) {
parent[0][u] = p;
for (int v : graph[u]) {
if (v != p) {
depth[v] = depth[u] + 1;
dfs(v, u, graph, parent, depth);
}
}
}
private int lca(int u, int v, int[][] parent, int[] depth) {
if (depth[u] < depth[v]) {
final int temp = u;
u = v;
v = temp;
}
for (int k = LOG - 1; k >= 0; --k)
if (parent[k][u] != -1 && depth[parent[k][u]] >= depth[v])
u = parent[k][u];
if (u == v)
return u;
for (int k = LOG - 1; k >= 0; --k)
if (parent[k][u] != -1 && parent[k][u] != parent[k][v]) {
u = parent[k][u];
v = parent[k][v];
}
return parent[0][u];
}
private int modPow(long x, long n) {
if (n == 0)
return 1;
if (n % 2 == 1)
return (int) (x * modPow(x % MOD, (n - 1)) % MOD);
return modPow(x * x % MOD, (n / 2)) % MOD;
}
}
// code provided by PROGIEZ3559. Number of Ways to Assign Edge Weights II LeetCode Solution in Python
class Solution:
def assignEdgeWeights(
self,
edges: list[list[int]],
queries: list[list[int]]
) -> list[int]:
MOD = 1_000_000_007
LOG = 17 # since 2^17 > 1e5
n = len(edges) + 1
ans = []
depth = [0] * (n + 1)
graph = [[] for _ in range(n + 1)]
parent = [[-1] * (n + 1) for _ in range(LOG)]
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
def dfs(u: int, p: int) -> None:
parent[0][u] = p
for v in graph[u]:
if v != p:
depth[v] = depth[u] + 1
dfs(v, u)
dfs(1, -1)
for k in range(1, LOG):
for v in range(1, n + 1):
if parent[k - 1][v] != -1:
parent[k][v] = parent[k - 1][parent[k - 1][v]]
def lca(u: int, v: int) -> int:
if depth[u] < depth[v]:
u, v = v, u
for k in reversed(range(LOG)):
if parent[k][u] != -1 and depth[parent[k][u]] >= depth[v]:
u = parent[k][u]
if u == v:
return u
for k in reversed(range(LOG)):
if parent[k][u] != -1 and parent[k][u] != parent[k][v]:
u = parent[k][u]
v = parent[k][v]
return parent[0][u]
for u, v in queries:
if u == v:
ans.append(0)
else:
a = lca(u, v)
d = depth[u] + depth[v] - 2 * depth[a]
ans.append(pow(2, d - 1, MOD))
return ans
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.