Recomendamos encarecidamente consultar la publicación a continuación como requisito previo para esto.
Descomposición ligera pesada | Conjunto 1 (Introducción)
En la publicación anterior, discutimos la descomposición Heavy-light (HLD) con la ayuda del siguiente ejemplo.
Supongamos que tenemos un árbol desequilibrado (no necesariamente un árbol binario) de n Nodes , y tenemos que realizar operaciones en el árbol para responder a una serie de consultas, cada una puede ser de uno de los dos tipos:
- change(a, b) : Actualiza el peso del a -ésimo borde a b.
- maxEdge(a, b) : Imprime el peso máximo del borde en la ruta desde el Node a hasta el Node b. Por ejemplo maxEdge(5, 10) debe imprimir 25.
En este artículo se discute la implementación de la misma
. Nuestra línea de ataque para este problema es:
- Creando el árbol
- Configurar el tamaño del subárbol, la profundidad y el padre para cada Node (usando un DFS)
- Descomponer el árbol en strings disjuntas
- Construyendo el árbol de segmentos
- Respondiendo consultas
1. Creación del árbol: la implementación utiliza la representación de array de adyacencia del árbol, para facilitar la comprensión. Se puede usar el representante de la lista de adyacencia con algunos cambios en la fuente. Si el número de arista e con peso w existe entre los Nodes u y v, almacenaremos e en árbol[u][v] y árbol[v][u], y el peso w en una array lineal separada de pesos de arista (n- 1 bordes).
2. Configuración del tamaño, la profundidad y el padre del subárbol para cada Node: A continuación, hacemos un DFS en el árbol para configurar arreglos que almacenen el tamaño y la profundidad del padre, el subárbol y la profundidad de cada Node. Otra cosa importante que hacemos en el momento de DFS es almacenar el Node más profundo de cada borde que atravesamos. Esto nos ayudará a la hora de actualizar el árbol (consulta change()).
3 y 4. Descomponer el árbol en strings separadas y construir un árbol de segmentosAhora viene la parte más importante: DAN. A medida que recorremos los bordes y llegamos a los Nodes (comenzando desde la raíz), colocamos el borde en la base del árbol del segmento, decidimos si el Node será la cabeza de una nueva string (si es un hijo normal) o será el actual extensión de string (hijo especial), almacene el ID de string al que pertenece el Node y almacene su lugar en la base del árbol de segmentos (para consultas futuras). La base para el árbol de segmentos se construye de manera que todos los bordes que pertenecen a la misma string estén juntos y las strings estén separadas por bordes claros.
Ilustración: Comenzamos en el Node 1. Como no había ningún borde por el cual llegamos a este Node, insertamos ‘-1’ como el peso del borde imaginario, en la array que actuará como base para el árbol de segmentos.
A continuación, nos movemos al hijo especial del Node 1, que es el Node 2, y dado que atravesamos el borde con peso 13, agregamos 13 a nuestra array base. El hijo especial del Node 2 es el Node 6. Atravesamos el borde con un peso de 25 para llegar al Node 6. Lo insertamos en la array base. Y de manera similar, extendemos esta string aún más mientras no hayamos llegado a un Node hoja (Node 10 en nuestro caso).
Luego cambiamos a un hijo normal del padre del último Node hoja y marcamos el comienzo de una nueva string. El padre aquí es el Node 8 y el hijo normal es el Node 11. Atravesamos el borde con peso 6 y lo insertamos en la array base. Así es como completamos la array base para el árbol de segmentos.
También recuerde que necesitamos almacenar la posición de cada Node en el árbol de segmentos para futuras consultas. La posición del Node 1 es 1, el Node 2 es 2, el Node 6 es 3, el Node 8 es 4, …, el Node 11 es 6, el Node 5 es 7, el Node 9 es 10, el Node 4 es 11 (indexación basada en 1).
5. Responder consultas
Hemos discutido la consulta mexEdge() en detalle en una publicación anterior . Para maxEdge(u, v), encontramos el borde de peso máximo en la ruta de u a LCA y v a LCA y devolvemos un máximo de dos.
Para la consulta de cambio() , podemos actualizar el árbol de segmentos utilizando el extremo más profundo del borde cuyo peso se actualizará. Encontraremos la posición del extremo más profundo del borde en la array que actúa como base para el árbol de segmentos y luego comenzaremos nuestra actualización desde ese Node y nos moveremos hacia arriba actualizando el árbol de segmentos. Digamos que queremos actualizar el borde 8 (entre el Node 7 y el Node 9) a 28. La posición del Node 9 más profundo en la array base es 10. Lo hacemos de la siguiente manera:
A continuación se muestra la implementación en C++ de los pasos anteriores.
CPP
/* C++ program for Heavy-Light Decomposition of a tree */
#include<bits/stdc++.h>
using namespace std;
#define N 1024
int tree[N][N]; // Matrix representing the tree
/* a tree node structure. Every node has a parent, depth,
subtree size, chain to which it belongs and a position
in base array*/
struct treeNode
{
int par; // Parent of this node
int depth; // Depth of this node
int size; // Size of subtree rooted with this node
int pos_segbase; // Position in segment tree base
int chain;
} node[N];
/* every Edge has a weight and two ends. We store deeper end */
struct Edge
{
int weight; // Weight of Edge
int deeper_end; // Deeper end
} edge[N];
/* we construct one segment tree, on base array */
struct segmentTree
{
int base_array[N], tree[6*N];
} s;
// A function to add Edges to the Tree matrix
// e is Edge ID, u and v are the two nodes, w is weight
void addEdge(int e, int u, int v, int w)
{
/*tree as undirected graph*/
tree[u-1][v-1] = e-1;
tree[v-1][u-1] = e-1;
edge[e-1].weight = w;
}
// A recursive function for DFS on the tree
// curr is the current node, prev is the parent of curr,
// dep is its depth
void dfs(int curr, int prev, int dep, int n)
{
/* set parent of current node to predecessor*/
node[curr].par = prev;
node[curr].depth = dep;
node[curr].size = 1;
/* for node's every child */
for (int j=0; j<n; j++)
{
if (j!=curr && j!=node[curr].par && tree[curr][j]!=-1)
{
/* set deeper end of the Edge as this child*/
edge[tree[curr][j]].deeper_end = j;
/* do a DFS on subtree */
dfs(j, curr, dep+1, n);
/* update subtree size */
node[curr].size+=node[j].size;
}
}
}
// A recursive function that decomposes the Tree into chains
void hld(int curr_node, int id, int *edge_counted, int *curr_chain,
int n, int chain_heads[])
{
/* if the current chain has no head, this node is the first node
* and also chain head */
if (chain_heads[*curr_chain]==-1)
chain_heads[*curr_chain] = curr_node;
/* set chain ID to which the node belongs */
node[curr_node].chain = *curr_chain;
/* set position of node in the array acting as the base to
the segment tree */
node[curr_node].pos_segbase = *edge_counted;
/* update array which is the base to the segment tree */
s.base_array[(*edge_counted)++] = edge[id].weight;
/* Find the special child (child with maximum size) */
int spcl_chld = -1, spcl_edg_id;
for (int j=0; j<n; j++)
if (j!=curr_node && j!=node[curr_node].par && tree[curr_node][j]!=-1)
if (spcl_chld==-1 || node[spcl_chld].size < node[j].size)
spcl_chld = j, spcl_edg_id = tree[curr_node][j];
/* if special child found, extend chain */
if (spcl_chld!=-1)
hld(spcl_chld, spcl_edg_id, edge_counted, curr_chain, n, chain_heads);
/* for every other (normal) child, do HLD on child subtree as separate
chain*/
for (int j=0; j<n; j++)
{
if (j!=curr_node && j!=node[curr_node].par &&
j!=spcl_chld && tree[curr_node][j]!=-1)
{
(*curr_chain)++;
hld(j, tree[curr_node][j], edge_counted, curr_chain, n, chain_heads);
}
}
}
// A recursive function that constructs Segment Tree for array[ss..se).
// si is index of current node in segment tree st
int construct_ST(int ss, int se, int si)
{
// If there is one element in array, store it in current node of
// segment tree and return
if (ss == se-1)
{
s.tree[si] = s.base_array[ss];
return s.base_array[ss];
}
// If there are more than one elements, then recur for left and
// right subtrees and store the minimum of two values in this node
int mid = (ss + se)/2;
s.tree[si] = max(construct_ST(ss, mid, si*2),
construct_ST(mid, se, si*2+1));
return s.tree[si];
}
// A recursive function that updates the Segment Tree
// x is the node to be updated to value val
// si is the starting index of the segment tree
// ss, se mark the corners of the range represented by si
int update_ST(int ss, int se, int si, int x, int val)
{
if(ss > x || se <= x);
else if(ss == x && ss == se-1)s.tree[si] = val;
else
{
int mid = (ss + se)/2;
s.tree[si] = max(update_ST(ss, mid, si*2, x, val),
update_ST(mid, se, si*2+1, x, val));
}
return s.tree[si];
}
// A function to update Edge e's value to val in segment tree
void change(int e, int val, int n)
{
update_ST(0, n, 1, node[edge[e].deeper_end].pos_segbase, val);
// following lines of code make no change to our case as we are
// changing in ST above
// Edge_weights[e] = val;
// segtree_Edges_weights[deeper_end_of_edge[e]] = val;
}
// A function to get the LCA of nodes u and v
int LCA(int u, int v, int n)
{
/* array for storing path from u to root */
int LCA_aux[n+5];
// Set u is deeper node if it is not
if (node[u].depth < node[v].depth)
swap(u, v);
/* LCA_aux will store path from node u to the root*/
memset(LCA_aux, -1, sizeof(LCA_aux));
while (u!=-1)
{
LCA_aux[u] = 1;
u = node[u].par;
}
/* find first node common in path from v to root and u to
root using LCA_aux */
while (v)
{
if (LCA_aux[v]==1)break;
v = node[v].par;
}
return v;
}
/* A recursive function to get the minimum value in a given range
of array indexes. The following are parameters for this function.
st --> Pointer to segment tree
index --> Index of current node in the segment tree. Initially
0 is passed as root is always at index 0
ss & se --> Starting and ending indexes of the segment represented
by current node, i.e., st[index]
qs & qe --> Starting and ending indexes of query range */
int RMQUtil(int ss, int se, int qs, int qe, int index)
{
//printf("%d,%d,%d,%d,%d\n", ss, se, qs, qe, index);
// If segment of this node is a part of given range, then return
// the min of the segment
if (qs <= ss && qe >= se-1)
return s.tree[index];
// If segment of this node is outside the given range
if (se-1 < qs || ss > qe)
return -1;
// If a part of this segment overlaps with the given range
int mid = (ss + se)/2;
return max(RMQUtil(ss, mid, qs, qe, 2*index),
RMQUtil(mid, se, qs, qe, 2*index+1));
}
// Return minimum of elements in range from index qs (query start) to
// qe (query end). It mainly uses RMQUtil()
int RMQ(int qs, int qe, int n)
{
// Check for erroneous input values
if (qs < 0 || qe > n-1 || qs > qe)
{
printf("Invalid Input");
return -1;
}
return RMQUtil(0, n, qs, qe, 1);
}
// A function to move from u to v keeping track of the maximum
// we move to the surface changing u and chains
// until u and v donot belong to the same
int crawl_tree(int u, int v, int n, int chain_heads[])
{
int chain_u, chain_v = node[v].chain, ans = 0;
while (true)
{
chain_u = node[u].chain;
/* if the two nodes belong to same chain,
* we can query between their positions in the array
* acting as base to the segment tree. After the RMQ,
* we can break out as we have no where further to go */
if (chain_u==chain_v)
{
if (u==v); //trivial
else
ans = max(RMQ(node[v].pos_segbase+1, node[u].pos_segbase, n),
ans);
break;
}
/* else, we query between node u and head of the chain to which
u belongs and later change u to parent of head of the chain
to which u belongs indicating change of chain */
else
{
ans = max(ans,
RMQ(node[chain_heads[chain_u]].pos_segbase,
node[u].pos_segbase, n));
u = node[chain_heads[chain_u]].par;
}
}
return ans;
}
// A function for MAX_EDGE query
void maxEdge(int u, int v, int n, int chain_heads[])
{
int lca = LCA(u, v, n);
int ans = max(crawl_tree(u, lca, n, chain_heads),
crawl_tree(v, lca, n, chain_heads));
printf("%d\n", ans);
}
// driver function
int main()
{
/* fill adjacency matrix with -1 to indicate no connections */
memset(tree, -1, sizeof(tree));
int n = 11;
/* arguments in order: Edge ID, node u, node v, weight w*/
addEdge(1, 1, 2, 13);
addEdge(2, 1, 3, 9);
addEdge(3, 1, 4, 23);
addEdge(4, 2, 5, 4);
addEdge(5, 2, 6, 25);
addEdge(6, 3, 7, 29);
addEdge(7, 6, 8, 5);
addEdge(8, 7, 9, 30);
addEdge(9, 8, 10, 1);
addEdge(10, 8, 11, 6);
/* our tree is rooted at node 0 at depth 0 */
int root = 0, parent_of_root=-1, depth_of_root=0;
/* a DFS on the tree to set up:
* arrays for parent, depth, subtree size for every node;
* deeper end of every Edge */
dfs(root, parent_of_root, depth_of_root, n);
int chain_heads[N];
/*we have initialized no chain heads */
memset(chain_heads, -1, sizeof(chain_heads));
/* Stores number of edges for construction of segment
tree. Initially we haven't traversed any Edges. */
int edge_counted = 0;
/* we start with filling the 0th chain */
int curr_chain = 0;
/* HLD of tree */
hld(root, n-1, &edge_counted, &curr_chain, n, chain_heads);
/* ST of segregated Edges */
construct_ST(0, edge_counted, 1);
/* Since indexes are 0 based, node 11 means index 11-1,
8 means 8-1, and so on*/
int u = 11, v = 9;
cout << "Max edge between " << u << " and " << v << " is ";
maxEdge(u-1, v-1, n, chain_heads);
// Change value of edge number 8 (index 8-1) to 28
change(8-1, 28, n);
cout << "After Change: max edge between " << u << " and "
<< v << " is ";
maxEdge(u-1, v-1, n, chain_heads);
v = 4;
cout << "Max edge between " << u << " and " << v << " is ";
maxEdge(u-1, v-1, n, chain_heads);
// Change value of edge number 5 (index 5-1) to 22
change(5-1, 22, n);
cout << "After Change: max edge between " << u << " and "
<< v << " is ";
maxEdge(u-1, v-1, n, chain_heads);
return 0;
}
Java
/* Java program for Heavy-Light Decomposition of a tree */
import java.util.*;
class GFG
{
static final int N = 1024;
static int edge_counted;
static int curr_chain;
static int [][]tree = new int[N][N]; // Matrix representing the tree
/* a tree node structure. Every node has a parent, depth,
subtree size, chain to which it belongs and a position
in base array*/
static class treeNode
{
int par; // Parent of this node
int depth; // Depth of this node
int size; // Size of subtree rooted with this node
int pos_segbase; // Position in segment tree base
int chain;
} ;
static treeNode node[] = new treeNode[N];
/* every Edge has a weight and two ends. We store deeper end */
static class Edge
{
int weight; // Weight of Edge
int deeper_end; // Deeper end
Edge(int weight, int deeper_end)
{
this.weight = weight;
this.deeper_end = deeper_end;
}
} ;
static Edge edge[] = new Edge[N];
/* we conone segment tree, on base array */
static class segmentTree
{
int []base_array = new int[N];
int []tree = new int[6*N];
} ;
static segmentTree s = new segmentTree();
// A function to add Edges to the Tree matrix
// e is Edge ID, u and v are the two nodes, w is weight
static void addEdge(int e, int u, int v, int w)
{
/*tree as undirected graph*/
tree[u - 1][v - 1] = e - 1;
tree[v - 1][u - 1] = e - 1;
edge[e - 1].weight = w;
}
// A recursive function for DFS on the tree
// curr is the current node, prev is the parent of curr,
// dep is its depth
static void dfs(int curr, int prev, int dep, int n)
{
/* set parent of current node to predecessor*/
node[curr].par = prev;
node[curr].depth = dep;
node[curr].size = 1;
/* for node's every child */
for (int j = 0; j < n; j++)
{
if (j != curr && j != node[curr].par && tree[curr][j] != -1)
{
/* set deeper end of the Edge as this child*/
edge[tree[curr][j]].deeper_end = j;
/* do a DFS on subtree */
dfs(j, curr, dep + 1, n);
/* update subtree size */
node[curr].size += node[j].size;
}
}
}
// A recursive function that decomposes the Tree into chains
static void hld(int curr_node, int id,
int n, int chain_heads[])
{
/* if the current chain has no head, this node is the first node
* and also chain head */
if (chain_heads[curr_chain] == -1)
chain_heads[curr_chain] = curr_node;
/* set chain ID to which the node belongs */
node[curr_node].chain = curr_chain;
/* set position of node in the array acting as the base to
the segment tree */
node[curr_node].pos_segbase = edge_counted;
/* update array which is the base to the segment tree */
s.base_array[(edge_counted)++] = edge[id].weight;
/* Find the special child (child with maximum size) */
int spcl_chld = -1, spcl_edg_id = 0;
for (int j = 0; j < n; j++)
if (j != curr_node && j != node[curr_node].par && tree[curr_node][j] != -1)
if (spcl_chld == -1 || node[spcl_chld].size < node[j].size)
{
spcl_chld = j; spcl_edg_id = tree[curr_node][j];
}
/* if special child found, extend chain */
if (spcl_chld != -1)
hld(spcl_chld, spcl_edg_id, n, chain_heads);
/* for every other (normal) child, do HLD on child subtree as separate
chain*/
for (int j = 0; j < n; j++)
{
if (j != curr_node && j != node[curr_node].par &&
j != spcl_chld && tree[curr_node][j] != -1)
{
(curr_chain)++;
hld(j, tree[curr_node][j], n, chain_heads);
}
}
}
// A recursive function that constructs Segment Tree for array[ss..se).
// si is index of current node in segment tree st
static int construct_ST(int ss, int se, int si)
{
// If there is one element in array, store it in current node of
// segment tree and return
if (ss == se - 1)
{
s.tree[si] = s.base_array[ss];
return s.base_array[ss];
}
// If there are more than one elements, then recur for left and
// right subtrees and store the minimum of two values in this node
int mid = (ss + se) / 2;
s.tree[si] = Math.max(construct_ST(ss, mid, si * 2),
construct_ST(mid, se, si * 2 + 1));
return s.tree[si];
}
// A recursive function that updates the Segment Tree
// x is the node to be updated to value val
// si is the starting index of the segment tree
// ss, se mark the corners of the range represented by si
static int update_ST(int ss, int se, int si, int x, int val)
{
if(ss > x || se <= x);
else if(ss == x && ss == se - 1)s.tree[si] = val;
else
{
int mid = (ss + se) / 2;
s.tree[si] = Math.max(update_ST(ss, mid, si * 2, x, val),
update_ST(mid, se, si * 2 + 1, x, val));
}
return s.tree[si];
}
// A function to update Edge e's value to val in segment tree
static void change(int e, int val, int n)
{
update_ST(0, n, 1, node[edge[e].deeper_end].pos_segbase, val);
// following lines of code make no change to our case as we are
// changing in ST above
// Edge_weights[e] = val;
// segtree_Edges_weights[deeper_end_of_edge[e]] = val;
}
// A function to get the LCA of nodes u and v
static int LCA(int u, int v, int n)
{
/* array for storing path from u to root */
int []LCA_aux= new int[n + 5];
// Set u is deeper node if it is not
if (node[u].depth < node[v].depth)
{
int t = u;
u = v;
v = t;
}
/* LCA_aux will store path from node u to the root*/
Arrays.fill(LCA_aux, -1);
while (u != -1)
{
LCA_aux[u] = 1;
u = node[u].par;
}
/* find first node common in path from v to root and u to
root using LCA_aux */
while (v > 0)
{
if (LCA_aux[v] == 1)break;
v = node[v].par;
}
return v;
}
/* A recursive function to get the minimum value in a given range
of array indexes. The following are parameters for this function.
st -. Pointer to segment tree
index -. Index of current node in the segment tree. Initially
0 is passed as root is always at index 0
ss & se -. Starting and ending indexes of the segment represented
by current node, i.e., st[index]
qs & qe -. Starting and ending indexes of query range */
static int RMQUtil(int ss, int se, int qs, int qe, int index)
{
//System.out.printf("%d,%d,%d,%d,%d\n", ss, se, qs, qe, index);
// If segment of this node is a part of given range, then return
// the min of the segment
if (qs <= ss && qe >= se - 1)
return s.tree[index];
// If segment of this node is outside the given range
if (se - 1 < qs || ss > qe)
return -1;
// If a part of this segment overlaps with the given range
int mid = (ss + se)/2;
return Math.max(RMQUtil(ss, mid, qs, qe, 2 * index),
RMQUtil(mid, se, qs, qe, 2 * index + 1));
}
// Return minimum of elements in range from index qs (query start) to
// qe (query end). It mainly uses RMQUtil()
static int RMQ(int qs, int qe, int n)
{
// Check for erroneous input values
if (qs < 0 || qe > n-1 || qs > qe)
{
System.out.printf("Invalid Input");
return -1;
}
return RMQUtil(0, n, qs, qe, 1);
}
// A function to move from u to v keeping track of the maximum
// we move to the surface changing u and chains
// until u and v donot belong to the same
static int crawl_tree(int u, int v, int n, int chain_heads[])
{
int chain_u, chain_v = node[v].chain, ans = 0;
while (true)
{
chain_u = node[u].chain;
/* if the two nodes belong to same chain,
* we can query between their positions in the array
* acting as base to the segment tree. After the RMQ,
* we can break out as we have no where further to go */
if (chain_u == chain_v)
{
if (u == v); //trivial
else
ans = Math.max(RMQ(node[v].pos_segbase + 1, node[u].pos_segbase, n),
ans);
break;
}
/* else, we query between node u and head of the chain to which
u belongs and later change u to parent of head of the chain
to which u belongs indicating change of chain */
else
{
ans = Math.max(ans,
RMQ(node[chain_heads[chain_u]].pos_segbase,
node[u].pos_segbase, n));
u = node[chain_heads[chain_u]].par;
}
}
return ans;
}
// A function for MAX_EDGE query
static void maxEdge(int u, int v, int n, int chain_heads[])
{
int lca = LCA(u, v, n);
int ans = Math.max(crawl_tree(u, lca, n, chain_heads),
crawl_tree(v, lca, n, chain_heads));
System.out.printf("%d\n", ans);
}
// driver function
public static void main(String[] args)
{
/* fill adjacency matrix with -1 to indicate no connections */
for(int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
tree[i][j] = -1;
}
}
int n = 11;
for(int i = 0; i < edge.length; i++)
{
edge[i] = new Edge(0, 0);
}
for(int i = 0; i < node.length; i++)
{
node[i] = new treeNode();
}
/* arguments in order: Edge ID, node u, node v, weight w*/
addEdge(1, 1, 2, 13);
addEdge(2, 1, 3, 9);
addEdge(3, 1, 4, 23);
addEdge(4, 2, 5, 4);
addEdge(5, 2, 6, 25);
addEdge(6, 3, 7, 29);
addEdge(7, 6, 8, 5);
addEdge(8, 7, 9, 30);
addEdge(9, 8, 10, 1);
addEdge(10, 8, 11, 6);
/* our tree is rooted at node 0 at depth 0 */
int root = 0, parent_of_root = -1, depth_of_root = 0;
/* a DFS on the tree to set up:
* arrays for parent, depth, subtree size for every node;
* deeper end of every Edge */
dfs(root, parent_of_root, depth_of_root, n);
int []chain_heads = new int[N];
/*we have initialized no chain heads */
Arrays.fill(chain_heads, -1);
/* Stores number of edges for construction of segment
tree. Initially we haven't traversed any Edges. */
edge_counted = 0;
/* we start with filling the 0th chain */
curr_chain = 0;
/* HLD of tree */
hld(root, n - 1, n, chain_heads);
/* ST of segregated Edges */
construct_ST(0, edge_counted, 1);
/* Since indexes are 0 based, node 11 means index 11-1,
8 means 8-1, and so on*/
int u = 11, v = 9;
System.out.print("Max edge between " + u + " and " + v + " is ");
maxEdge(u - 1, v - 1, n, chain_heads);
// Change value of edge number 8 (index 8-1) to 28
change(8 - 1, 28, n);
System.out.print("After Change: max edge between " + u + " and "
+ v + " is ");
maxEdge(u - 1, v - 1, n, chain_heads);
v = 4;
System.out.print("Max edge between " + u + " and " + v + " is ");
maxEdge(u - 1, v - 1, n, chain_heads);
// Change value of edge number 5 (index 5-1) to 22
change(5 - 1, 22, n);
System.out.print("After Change: max edge between " + u + " and "
+ v + " is ");
maxEdge(u - 1, v - 1, n, chain_heads);
}
}
// This code contributed by Rajput-Ji
Producción:
Max edge between 11 and 9 is 30 After Change: max edge between 11 and 9 is 29 Max edge between 11 and 4 is 25 After Change: max edge between 11 and 4 is 23
Este artículo es una contribución de Yash Varyani . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA