Dado un árbol , y los pesos de todos los Nodes. Cada consulta contiene dos enteros u y v , la tarea es encontrar el peso mínimo y máximo en la ruta simple entre u y v (ambos inclusive).
Ejemplos:
Aporte:
Consulta=[{1, 3}, {2, 4}, {3, 5}]
Salida:
-1 5
3 5
-2 5
Explicación:
El peso en la ruta 1 a 3 es [-1, 5, -1]. Por lo tanto, el peso mínimo y máximo es -1 y 5 respectivamente.
El peso en la ruta 2 a 4 es [5, 3]. Por lo tanto, el peso mínimo y máximo es 3 y 5 respectivamente.
El peso en la ruta 2 a 4 es [-1, 5, -1, -2]. Por lo tanto, el peso mínimo y máximo es -2 y 5 respectivamente.
Enfoque: La idea es usar LCA en un árbol usando la técnica de elevación binaria.
- Binary Lifting es un enfoque de programación dinámica en el que precalculamos una array lca[i][j] donde i = [1, n], j = [1, log(n)] y lca[i][j] contiene 2 j -ésimo ancestro del Node i.
- Para calcular los valores de lca[][], se puede usar la siguiente recursión
lca[i][j] = padre[i] si j = 0 y
lca[i][j] = lca[lca[i][j – 1]][j – 1] si j > 0.
- Como calcularemos la array lca[][], también calcularemos MinWeight[][] y MaxWeight[][] donde MinWeight[i][j] contiene el peso mínimo desde el Node i hasta su 2 j -ésimo ancestro, y MaxWeight[i][j] contiene el peso máximo desde el Node i hasta su 2 j -th ancestro
- Para calcular los valores de MinWeight[][] y MaxWeight[], se puede utilizar la siguiente recursión.
![MinWeight[i][j] =\begin{cases} min (weight[i], weight[parent[i]]) & \text{ ;if } j=0 \\ min( MinWeight[i][j-1], MinWeight[lca[i][j - 1]][j - 1]) & \text{ ;if } j>0 \end{cases}](https://www.geeksforgeeks.org/wp-content/ql-cache/quicklatex.com-126cd8b7c4922d065d9235f4239ac30b_l3.png "Rendered by QuickLaTeX.com")
[Tex]MaxWeight[i][j] =\begin{cases} max (weight[i], weight[parent[i]]) & \text{ ;if } j=0 \\ max( MaxWeight[i][j-1], MaxWeight[lca[i][j – 1]][j – 1]) & \text{ ;if } j>0 \end{cases} [/Tex]
- Después del precálculo encontramos el peso mínimo y máximo entre (u, v) como encontramos el antepasado mínimo común de (u, v).
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to find the maximum and
// minimum weight between two nodes
// in the given tree using LCA
#include <bits/stdc++.h>
using namespace std;
#define MAX 1000
#define log 10 // log2(MAX)
// Array to store the level
// of each node
int level[MAX];
int lca[MAX][log];
int minWeight[MAX][log];
int maxWeight[MAX][log];
// Vector to store tree
vector<int> graph[MAX];
// Array to store weight of nodes
int weight[MAX];
void addEdge(int u, int v)
{
graph[u].push_back(v);
graph[v].push_back(u);
}
// Pre-Processing to calculate
// values of lca[][], MinWeight[][]
// and MaxWeight[][]
void dfs(int node, int parent, int h)
{
// Using recursion formula to
// calculate the values
// of lca[][]
lca[node][0] = parent;
// Storing the level of
// each node
level[node] = h;
if (parent != -1)
{
minWeight[node][0]
= min(weight[node], weight[parent]);
maxWeight[node][0]
= max(weight[node], weight[parent]);
}
for (int i = 1; i < log; i++)
{
if (lca[node][i - 1] != -1)
{
// Using recursion formula to
// calculate the values of lca[][],
// MinWeight[][] and MaxWeight[][]
lca[node][i] = lca[lca[node][i - 1]][i - 1];
minWeight[node][i]
= min(minWeight[node][i - 1],
minWeight[lca[node][i - 1]][i - 1]);
maxWeight[node][i]
= max(maxWeight[node][i - 1],
maxWeight[lca[node][i - 1]][i - 1]);
}
}
for (int i : graph[node])
{
if (i == parent)
continue;
dfs(i, node, h + 1);
}
}
// Function to find the minimum and
// maximum weights in the given range
void findMinMaxWeight(int u, int v)
{
int minWei = INT_MAX;
int maxWei = INT_MIN;
// The node which is present
// farthest from the root node
// is taken as v If u is
// farther from root node
// then swap the two
if (level[u] > level[v])
swap(u, v);
// Finding the ancestor of v
// which is at same level as u
for (int i = log - 1; i >= 0; i--)
{
if (lca[v][i] != -1
&& level[lca[v][i]] >= level[u])
{
// Calculating Minimum and
// Maximum Weight of node
// v till its 2^i-th ancestor
minWei = min(minWei, minWeight[v][i]);
maxWei = max(maxWei, maxWeight[v][i]);
v = lca[v][i];
}
}
// If u is the ancestor of v
// then u is the LCA of u and v
if (v == u)
{
cout << minWei << " " << maxWei << endl;
}
else {
// Finding the node closest to the
// root which is not the common
// ancestor of u and v i.e. a node
// x such that x is not the common
// ancestor of u and v but lca[x][0] is
for (int i = log - 1; i >= 0; i--)
{
if (lca[v][i] != lca[u][i])
{
// Calculating the minimum of
// MinWeight of v to its 2^i-th
// ancestor and MinWeight of u
// to its 2^i-th ancestor
minWei = min(minWei, min(minWeight[v][i],
minWeight[u][i]));
// Calculating the maximum of
// MaxWeight of v to its 2^i-th
// ancestor and MaxWeight of u
// to its 2^i-th ancestor
maxWei = max(maxWei, max(maxWeight[v][i],
maxWeight[u][i]));
v = lca[v][i];
u = lca[u][i];
}
}
// Calculating the Minimum of
// first ancestor of u and v
minWei = min(minWei,
min(minWeight[v][0], minWeight[u][0]));
// Calculating the maximum of
// first ancestor of u and v
maxWei = max(maxWei,
max(maxWeight[v][0], maxWeight[u][0]));
cout << minWei << " " << maxWei << endl;
}
}
// Driver Code
int main()
{
// Number of nodes
int n = 5;
// Add edges
addEdge(1, 2);
addEdge(1, 5);
addEdge(2, 4);
addEdge(2, 3);
weight[1] = -1;
weight[2] = 5;
weight[3] = -1;
weight[4] = 3;
weight[5] = -2;
// Initialising lca values with -1
// Initialising MinWeight values
// with INT_MAX
// Initialising MaxWeight values
// with INT_MIN
for (int i = 1; i <= n; i++) {
for (int j = 0; j < log; j++) {
lca[i][j] = -1;
minWeight[i][j] = INT_MAX;
maxWeight[i][j] = INT_MIN;
}
}
// Perform DFS
dfs(1, -1, 0);
// Query 1: {1, 3}
findMinMaxWeight(1, 3);
// Query 2: {2, 4}
findMinMaxWeight(2, 4);
// Query 3: {3, 5}
findMinMaxWeight(3, 5);
return 0;
}
Java
// Java Program to find the maximum and
// minimum weight between two nodes
// in the given tree using LCA
import java.util.*;
class GFG{
static final int MAX = 1000;
// Math.log(MAX)
static final int log = 10 ;
// Array to store the
// level of each node
static int []level =
new int[MAX];
static int [][]lca =
new int[MAX][log];
static int [][]minWeight =
new int[MAX][log];
static int [][]maxWeight =
new int[MAX][log];
// Vector to store tree
static Vector<Integer> []graph =
new Vector[MAX];
// Array to store
// weight of nodes
static int []weight =
new int[MAX];
private static void swap(int x,
int y)
{
int temp = x;
x = y;
y = temp;
}
static void addEdge(int u,
int v)
{
graph[u].add(v);
graph[v].add(u);
}
// Pre-Processing to
// calculate values of
// lca[][], MinWeight[][]
// and MaxWeight[][]
static void dfs(int node,
int parent, int h)
{
// Using recursion formula to
// calculate the values
// of lca[][]
lca[node][0] = parent;
// Storing the level of
// each node
level[node] = h;
if (parent != -1)
{
minWeight[node][0] = Math.min(weight[node],
weight[parent]);
maxWeight[node][0] = Math.max(weight[node],
weight[parent]);
}
for (int i = 1; i < log; i++)
{
if (lca[node][i - 1] != -1)
{
// Using recursion formula to
// calculate the values of lca[][],
// MinWeight[][] and MaxWeight[][]
lca[node][i] =
lca[lca[node][i - 1]][i - 1];
minWeight[node][i] =
Math.min(minWeight[node][i - 1],
minWeight[lca[node][i - 1]][i - 1]);
maxWeight[node][i] =
Math.max(maxWeight[node][i - 1],
maxWeight[lca[node][i - 1]][i - 1]);
}
}
for (int i : graph[node])
{
if (i == parent)
continue;
dfs(i, node, h + 1);
}
}
// Function to find the minimum and
// maximum weights in the given range
static void findMinMaxWeight(int u,
int v)
{
int minWei = Integer.MAX_VALUE;
int maxWei = Integer.MIN_VALUE;
// The node which is present
// farthest from the root node
// is taken as v If u is
// farther from root node
// then swap the two
if (level[u] > level[v])
swap(u, v);
// Finding the ancestor of v
// which is at same level as u
for (int i = log - 1; i >= 0; i--)
{
if (lca[v][i] != -1 &&
level[lca[v][i]] >= level[u])
{
// Calculating Minimum and
// Maximum Weight of node
// v till its 2^i-th ancestor
minWei = Math.min(minWei,
minWeight[v][i]);
maxWei = Math.max(maxWei,
maxWeight[v][i]);
v = lca[v][i];
}
}
// If u is the ancestor of v
// then u is the LCA of u and v
if (v == u)
{
System.out.print(minWei + " " +
maxWei + "\n");
}
else
{
// Finding the node closest to the
// root which is not the common
// ancestor of u and v i.e. a node
// x such that x is not the common
// ancestor of u and v but lca[x][0] is
for (int i = log - 1; i >= 0; i--)
{
if(v == -1)
v++;
if (lca[v][i] != lca[u][i])
{
// Calculating the minimum of
// MinWeight of v to its 2^i-th
// ancestor and MinWeight of u
// to its 2^i-th ancestor
minWei = Math.min(minWei,
Math.min(minWeight[v][i],
minWeight[u][i]));
// Calculating the maximum of
// MaxWeight of v to its 2^i-th
// ancestor and MaxWeight of u
// to its 2^i-th ancestor
maxWei = Math.max(maxWei,
Math.max(maxWeight[v][i],
maxWeight[u][i]));
v = lca[v][i];
u = lca[u][i];
}
}
// Calculating the Minimum of
// first ancestor of u and v
if(u == -1)
u++;
minWei = Math.min(minWei,
Math.min(minWeight[v][0],
minWeight[u][0]));
// Calculating the maximum of
// first ancestor of u and v
maxWei = Math.max(maxWei,
Math.max(maxWeight[v][0],
maxWeight[u][0]));
System.out.print(minWei + " " +
maxWei + "\n");
}
}
// Driver Code
public static void main(String[] args)
{
// Number of nodes
int n = 5;
for (int i = 0; i < graph.length; i++)
graph[i] = new Vector<Integer>();
// Add edges
addEdge(1, 2);
addEdge(1, 5);
addEdge(2, 4);
addEdge(2, 3);
weight[1] = -1;
weight[2] = 5;
weight[3] = -1;
weight[4] = 3;
weight[5] = -2;
// Initialising lca values with -1
// Initialising MinWeight values
// with Integer.MAX_VALUE
// Initialising MaxWeight values
// with Integer.MIN_VALUE
for (int i = 1; i <= n; i++)
{
for (int j = 0; j < log; j++)
{
lca[i][j] = -1;
minWeight[i][j] = Integer.MAX_VALUE;
maxWeight[i][j] = Integer.MIN_VALUE;
}
}
// Perform DFS
dfs(1, -1, 0);
// Query 1: {1, 3}
findMinMaxWeight(1, 3);
// Query 2: {2, 4}
findMinMaxWeight(2, 4);
// Query 3: {3, 5}
findMinMaxWeight(3, 5);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 Program to find the
# maximum and minimum weight
# between two nodes in the
# given tree using LCA
import sys
MAX = 1000
# log2(MAX)
log = 10
# Array to store the level
# of each node
level = [0 for i in range(MAX)];
# Initialising lca values with -1
# Initialising MinWeight values
# with INT_MAX
# Initialising MaxWeight values
# with INT_MIN
lca = [[-1 for j in range(log)]
for i in range(MAX)]
minWeight = [[sys.maxsize for j in range(log)]
for i in range(MAX)]
maxWeight = [[-sys.maxsize for j in range(log)]
for i in range(MAX)]
# Vector to store tree
graph = [[] for i in range(MAX)]
# Array to store weight of nodes
weight = [0 for i in range(MAX)]
def addEdge(u, v):
graph[u].append(v);
graph[v].append(u);
# Pre-Processing to calculate
# values of lca[][], MinWeight[][]
# and MaxWeight[][]
def dfs(node, parent, h):
# Using recursion formula to
# calculate the values
# of lca[][]
lca[node][0] = parent;
# Storing the level of
# each node
level[node] = h;
if (parent != -1):
minWeight[node][0] = (min(weight[node],
weight[parent]));
maxWeight[node][0] = (max(weight[node],
weight[parent]));
for i in range(1, log):
if (lca[node][i - 1] != -1):
# Using recursion formula to
# calculate the values of lca[][],
# MinWeight[][] and MaxWeight[][]
lca[node][i] = lca[lca[node][i - 1]][i - 1];
minWeight[node][i] = min(minWeight[node][i - 1],
minWeight[lca[node][i - 1]][i - 1]);
maxWeight[node][i] = max(maxWeight[node][i - 1],
maxWeight[lca[node][i - 1]][i - 1]);
for i in graph[node]:
if (i == parent):
continue;
dfs(i, node, h + 1);
# Function to find the minimum
# and maximum weights in the
# given range
def findMinMaxWeight(u, v):
minWei = sys.maxsize
maxWei = -sys.maxsize
# The node which is present
# farthest from the root node
# is taken as v If u is
# farther from root node
# then swap the two
if (level[u] > level[v]):
u, v = v, u
# Finding the ancestor of v
# which is at same level as u
for i in range(log - 1, -1, -1):
if (lca[v][i] != -1 and
level[lca[v][i]] >=
level[u]):
# Calculating Minimum and
# Maximum Weight of node
# v till its 2^i-th ancestor
minWei = min(minWei,
minWeight[v][i]);
maxWei = max(maxWei,
maxWeight[v][i]);
v = lca[v][i];
# If u is the ancestor of v
# then u is the LCA of u and v
if (v == u):
print(str(minWei) + ' ' +
str(maxWei))
else:
# Finding the node closest to the
# root which is not the common
# ancestor of u and v i.e. a node
# x such that x is not the common
# ancestor of u and v but lca[x][0] is
for i in range(log - 1, -1, -1):
if (lca[v][i] != lca[u][i]):
# Calculating the minimum of
# MinWeight of v to its 2^i-th
# ancestor and MinWeight of u
# to its 2^i-th ancestor
minWei = (min(minWei,
min(minWeight[v][i],
minWeight[u][i])));
# Calculating the maximum of
# MaxWeight of v to its 2^i-th
# ancestor and MaxWeight of u
# to its 2^i-th ancestor
maxWei = max(maxWei,
max(maxWeight[v][i],
maxWeight[u][i]));
v = lca[v][i];
u = lca[u][i];
# Calculating the Minimum of
# first ancestor of u and v
minWei = min(minWei,
min(minWeight[v][0],
minWeight[u][0]));
# Calculating the maximum of
# first ancestor of u and v
maxWei = max(maxWei,
max(maxWeight[v][0],
maxWeight[u][0]));
print(str(minWei) + ' ' +
str(maxWei))
# Driver code
if __name__ == "__main__":
# Number of nodes
n = 5;
# Add edges
addEdge(1, 2);
addEdge(1, 5);
addEdge(2, 4);
addEdge(2, 3);
weight[1] = -1;
weight[2] = 5;
weight[3] = -1;
weight[4] = 3;
weight[5] = -2;
# Perform DFS
dfs(1, -1, 0);
# Query 1: {1, 3}
findMinMaxWeight(1, 3);
# Query 2: {2, 4}
findMinMaxWeight(2, 4);
# Query 3: {3, 5}
findMinMaxWeight(3, 5);
# This code is contributed by Rutvik_56
C#
// C# Program to find the
// maximum and minimum
// weight between two nodes
// in the given tree using LCA
using System;
using System.Collections.Generic;
class GFG{
static readonly int MAX = 1000;
// Math.Log(MAX)
static readonly int log = 10 ;
// Array to store the
// level of each node
static int []level =
new int[MAX];
static int [,]lca =
new int[MAX, log];
static int [,]minWeight =
new int[MAX, log];
static int [,]maxWeight =
new int[MAX, log];
// List to store tree
static List<int> []graph =
new List<int>[MAX];
// Array to store
// weight of nodes
static int []weight =
new int[MAX];
private static void swap(int x,
int y)
{
int temp = x;
x = y;
y = temp;
}
static void addEdge(int u,
int v)
{
graph[u].Add(v);
graph[v].Add(u);
}
// Pre-Processing to
// calculate values of
// lca[,], MinWeight[,]
// and MaxWeight[,]
static void dfs(int node,
int parent, int h)
{
// Using recursion formula to
// calculate the values
// of lca[,]
lca[node, 0] = parent;
// Storing the level of
// each node
level[node] = h;
if (parent != -1)
{
minWeight[node, 0] = Math.Min(weight[node],
weight[parent]);
maxWeight[node, 0] = Math.Max(weight[node],
weight[parent]);
}
for (int i = 1; i < log; i++)
{
if (lca[node, i - 1] != -1)
{
// Using recursion formula to
// calculate the values of lca[,],
// MinWeight[,] and MaxWeight[,]
lca[node, i] =
lca[lca[node, i - 1],
i - 1];
minWeight[node, i] =
Math.Min(minWeight[node, i - 1],
minWeight[lca[node, i - 1],
i - 1]);
maxWeight[node, i] =
Math.Max(maxWeight[node, i - 1],
maxWeight[lca[node, i - 1],
i - 1]);
}
}
foreach (int i in graph[node])
{
if (i == parent)
continue;
dfs(i, node, h + 1);
}
}
// Function to find the minimum and
// maximum weights in the given range
static void findMinMaxWeight(int u,
int v)
{
int minWei = int.MaxValue;
int maxWei = int.MinValue;
// The node which is present
// farthest from the root node
// is taken as v If u is
// farther from root node
// then swap the two
if (level[u] > level[v])
swap(u, v);
// Finding the ancestor of v
// which is at same level as u
for (int i = log - 1; i >= 0; i--)
{
if (lca[v, i] != -1 &&
level[lca[v, i]] >= level[u])
{
// Calculating Minimum and
// Maximum Weight of node
// v till its 2^i-th ancestor
minWei = Math.Min(minWei,
minWeight[v, i]);
maxWei = Math.Max(maxWei,
maxWeight[v, i]);
v = lca[v, i];
}
}
// If u is the ancestor of v
// then u is the LCA of u and v
if (v == u)
{
Console.Write(minWei + " " +
maxWei + "\n");
}
else
{
// Finding the node closest to the
// root which is not the common
// ancestor of u and v i.e. a node
// x such that x is not the common
// ancestor of u and v but lca[x,0] is
for (int i = log - 1; i >= 0; i--)
{
if(v == -1)
v++;
if (lca[v, i] != lca[u, i])
{
// Calculating the minimum of
// MinWeight of v to its 2^i-th
// ancestor and MinWeight of u
// to its 2^i-th ancestor
minWei = Math.Min(minWei,
Math.Min(minWeight[v, i],
minWeight[u, i]));
// Calculating the maximum of
// MaxWeight of v to its 2^i-th
// ancestor and MaxWeight of u
// to its 2^i-th ancestor
maxWei = Math.Max(maxWei,
Math.Max(maxWeight[v, i],
maxWeight[u, i]));
v = lca[v, i];
u = lca[u, i];
}
}
// Calculating the Minimum of
// first ancestor of u and v
if(u == -1)
u++;
minWei = Math.Min(minWei,
Math.Min(minWeight[v, 0],
minWeight[u, 0]));
// Calculating the maximum of
// first ancestor of u and v
maxWei = Math.Max(maxWei,
Math.Max(maxWeight[v, 0],
maxWeight[u, 0]));
Console.Write(minWei + " " +
maxWei + "\n");
}
}
// Driver Code
public static void Main(String[] args)
{
// Number of nodes
int n = 5;
for (int i = 0; i < graph.Length; i++)
graph[i] = new List<int>();
// Add edges
addEdge(1, 2);
addEdge(1, 5);
addEdge(2, 4);
addEdge(2, 3);
weight[1] = -1;
weight[2] = 5;
weight[3] = -1;
weight[4] = 3;
weight[5] = -2;
// Initialising lca values with -1
// Initialising MinWeight values
// with int.MaxValue
// Initialising MaxWeight values
// with int.MinValue
for (int i = 1; i <= n; i++)
{
for (int j = 0; j < log; j++)
{
lca[i, j] = -1;
minWeight[i, j] = int.MaxValue;
maxWeight[i, j] = int.MinValue;
}
}
// Perform DFS
dfs(1, -1, 0);
// Query 1: {1, 3}
findMinMaxWeight(1, 3);
// Query 2: {2, 4}
findMinMaxWeight(2, 4);
// Query 3: {3, 5}
findMinMaxWeight(3, 5);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript Program to find the maximum and
// minimum weight between two nodes
// in the given tree using LCA
let MAX = 1000;
// Math.log(MAX)
let log = 10 ;
// Array to store the
// level of each node
let level = new Array(MAX);
level.fill(0);
let lca = new Array(MAX);
let minWeight = new Array(MAX);
let maxWeight = new Array(MAX);
// Vector to store tree
let graph = new Array(MAX);
// Array to store
// weight of nodes
let weight = new Array(MAX);
weight.fill(0);
function addEdge(u, v)
{
graph[u].push(v);
graph[v].push(u);
}
// Pre-Processing to
// calculate values of
// lca[][], MinWeight[][]
// and MaxWeight[][]
function dfs(node, parent, h)
{
// Using recursion formula to
// calculate the values
// of lca[][]
lca[node][0] = parent;
// Storing the level of
// each node
level[node] = h;
if (parent != -1)
{
minWeight[node][0] = Math.min(weight[node],
weight[parent]);
maxWeight[node][0] = Math.max(weight[node],
weight[parent]);
}
for (let i = 1; i < log; i++)
{
if (lca[node][i - 1] != -1)
{
// Using recursion formula to
// calculate the values of lca[][],
// MinWeight[][] and MaxWeight[][]
lca[node][i] =
lca[lca[node][i - 1]][i - 1];
minWeight[node][i] =
Math.min(minWeight[node][i - 1],
minWeight[lca[node][i - 1]][i - 1]);
maxWeight[node][i] =
Math.max(maxWeight[node][i - 1],
maxWeight[lca[node][i - 1]][i - 1]);
}
}
for (let i = 0; i < graph[node].length; i++)
{
if (graph[node][i] == parent)
continue;
dfs(graph[node][i], node, h + 1);
}
}
// Function to find the minimum and
// maximum weights in the given range
function findMinMaxWeight(u, v)
{
let minWei = Number.MAX_VALUE;
let maxWei = Number.MIN_VALUE;
// The node which is present
// farthest from the root node
// is taken as v If u is
// farther from root node
// then swap the two
if (level[u] > level[v])
{
let temp = u;
u = v;
v = temp;
}
// Finding the ancestor of v
// which is at same level as u
for (let i = log - 1; i >= 0; i--)
{
if (lca[v][i] != -1 &&
level[lca[v][i]] >= level[u])
{
// Calculating Minimum and
// Maximum Weight of node
// v till its 2^i-th ancestor
minWei = Math.min(minWei,
minWeight[v][i]);
maxWei = Math.max(maxWei,
maxWeight[v][i]);
v = lca[v][i];
}
}
// If u is the ancestor of v
// then u is the LCA of u and v
if (v == u)
{
document.write(minWei + " " + maxWei + "</br>");
}
else
{
// Finding the node closest to the
// root which is not the common
// ancestor of u and v i.e. a node
// x such that x is not the common
// ancestor of u and v but lca[x][0] is
for (let i = log - 1; i >= 0; i--)
{
if(v == -1)
v++;
if (lca[v][i] != lca[u][i])
{
// Calculating the minimum of
// MinWeight of v to its 2^i-th
// ancestor and MinWeight of u
// to its 2^i-th ancestor
minWei = Math.min(minWei,
Math.min(minWeight[v][i],
minWeight[u][i]));
// Calculating the maximum of
// MaxWeight of v to its 2^i-th
// ancestor and MaxWeight of u
// to its 2^i-th ancestor
maxWei = Math.max(maxWei,
Math.max(maxWeight[v][i],
maxWeight[u][i]));
v = lca[v][i];
u = lca[u][i];
}
}
// Calculating the Minimum of
// first ancestor of u and v
if(u == -1)
u++;
minWei = Math.min(minWei,
Math.min(minWeight[v][0],
minWeight[u][0]));
// Calculating the maximum of
// first ancestor of u and v
maxWei = Math.max(maxWei,
Math.max(maxWeight[v][0],
maxWeight[u][0]));
document.write(minWei + " " + maxWei + "</br>");
}
}
// Number of nodes
let n = 5;
for (let i = 0; i < graph.length; i++)
graph[i] = [];
// Add edges
addEdge(1, 2);
addEdge(1, 5);
addEdge(2, 4);
addEdge(2, 3);
weight[1] = -1;
weight[2] = 5;
weight[3] = -1;
weight[4] = 3;
weight[5] = -2;
// Initialising lca values with -1
// Initialising MinWeight values
// with Integer.MAX_VALUE
// Initialising MaxWeight values
// with Integer.MIN_VALUE
for (let i = 1; i <= n; i++)
{
lca[i] = new Array(log);
minWeight[i] = new Array(log);
maxWeight[i] = new Array(log);
for (let j = 0; j < log; j++)
{
lca[i][j] = -1;
minWeight[i][j] = Number.MAX_VALUE;
maxWeight[i][j] = Number.MIN_VALUE;
}
}
// Perform DFS
dfs(1, -1, 0);
// Query 1: {1, 3}
findMinMaxWeight(1, 3);
// Query 2: {2, 4}
findMinMaxWeight(2, 4);
// Query 3: {3, 5}
findMinMaxWeight(3, 5);
</script>
Producción
-1 5 3 5 -2 5
Complejidad de tiempo: el tiempo necesario para el preprocesamiento es O (N logN) y cada consulta lleva un tiempo O (logN) . Entonces, la complejidad temporal general de la solución es O(N logN) .
Publicación traducida automáticamente
Artículo escrito por saurabhshadow y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA