Dado un árbol con N Nodes y N-1 aristas con raíz en 1 y dado un arreglo de N-1 enteros. La tarea es asignar pesos a los bordes del árbol de modo que la suma de las distancias de cada Node a todos los demás Nodes sea máxima .
Ejemplos:
Aporte:
Salida: 46
Asigne el borde 1-2 con peso 5
Asigne el borde 2-3 con peso 7
Asigne el borde 3-4 con peso 1
La distancia del Node 1 a los Nodes 2, 3, 4 es {5, 5+7 , 5+7+1}
La distancia del Node 2 a los Nodes 3, 4 es {7, 7+1}
La distancia del Node 3 al Node 4 es {1}Aporte:
Salida: 94
Enfoque : el problema se puede resolver usando combinaciones , DFS , DP en árboles y lógica codiciosa . Dado que necesitamos asignar pesos a los bordes en el árbol, asignar el peso máximo al borde que ocurre la mayor cantidad de veces en todos los caminos será la forma de obtener la suma máxima. Para encontrar el número de veces que ocurre un borde en todos los caminos posibles, necesitamos saber el número de Nodes en ambos lados del borde. Sean c1 y c2 el conteo del número de Nodes en el lado izquierdo y derecho, entonces el número de veces que ocurre el borde en todos los caminos será c1 * c2. Ordena todos los valores posibles de c1 * c2 en orden ascendente. Asigne el peso máximo al valor máximo de c1 * c2, y a los demás de la misma manera. Podemos seguir los pasos a continuación para obtener la cantidad de Nodes en el lado izquierdo y en el lado derecho de un borde:
- Ejecute un dfs comenzando desde la raíz e inicialice una array dp[] que almacena el recuento de los Nodes en el subárbol de un Node determinado.
- Iterar para cada borde posible y encontrar el número de Nodes en ambos lados de los bordes.
- Para encontrar el número de Nodes en ambos lados, averigüe el valor más pequeño de dp[node1] o dp[node2] , donde node1 y node2 son los Nodes a ambos lados del borde
- Si un lado tiene min(dp[node1], dp[node2]) , entonces el otro lado tendrá (N – min(dp[node1], dp[node2])) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement the
// above approach
#include <bits/stdc++.h>
using namespace std;
// Function to add an edge to the tree
void addEdge(vector<pair<int, int> >& edges,
list<int>* tree, int x, int y)
{
edges.push_back({ x, y });
tree[x].push_back(y);
tree[y].push_back(x);
}
// Function to run DFS and calculate the
// height of the subtree below it
void dfs(vector<pair<int, int> >& edges, list<int>* tree,
int node, int parent, int dp[])
{
// Initially initialize with 1
dp[node] = 1;
// Traverse for all nodes connected to node
for (auto it : tree[node]) {
// If node is not parent
// then recall dfs
if (it != parent) {
dfs(edges, tree, it, node, dp);
// Add the size of the
// subtree beneath it
dp[node] += dp[it];
}
}
}
// Function to assign weights to edges
// to maximize the final sum
int maximizeSum(int a[], vector<pair<int, int> >& edges,
list<int>* tree, int n)
{
// Initialize it which stores the
// height of the subtree beneath it
int dp[n + 1] = { 0 };
// Call the DFS function to
dfs(edges, tree, 1, 0, dp);
// Sort the given array
sort(a, a + (n - 1));
// Stores the number of times an
// edge is part of a path
vector<int> ans;
// Iterate for all edges and find the
// number of nodes on the left and on the right
for (auto it : edges) {
// Node 1
int x = it.first;
// Node 2
int y = it.second;
// If the number of nodes below is less
// then the other will be n - dp[node]
if (dp[x] < dp[y]) {
int fi = dp[x];
int sec = n - dp[x];
ans.push_back(fi * sec);
}
// Second condition
else {
int fi = dp[y];
int sec = n - dp[y];
ans.push_back(fi * sec);
}
}
// Sort the number of times
// an edges occurs in the path
sort(ans.begin(), ans.end());
int res = 0;
// Find the summation of all those
// paths and return
for (int i = 0; i < n - 1; i++) {
res += ans[i] * a[i];
}
return res;
}
// Driver code
int main()
{
int n = 5;
vector<pair<int, int> > edges;
list<int>* tree = new list<int>[n + 1];
// Add an edge 1-2 in the tree
addEdge(edges, tree, 1, 2);
// Add an edge 2-3 in the tree
addEdge(edges, tree, 1, 3);
// Add an edge 3-4 in the tree
addEdge(edges, tree, 3, 4);
// Add an edge 3-5 in the tree
addEdge(edges, tree, 3, 5);
// Array which gives the edges weight
// to be assigned
int a[] = { 6, 3, 1, 9, 3 };
cout << maximizeSum(a, edges, tree, n);
}
Python3
# Python3 program to implement the # above approach edges = [[] for i in range(100)] tree = [[] for i in range(100)] # Function to add an edge to the tree def addEdge(x, y): edges.append([x, y]) tree[x].append(y) tree[y].append(x) # Function to run DFS and calculate the # height of the subtree below it def dfs(node, parent, dp): # Initially initialize with 1 dp[node] = 1 # Traverse for all nodes connected to node for it in tree[node]: # If node is not parent # then recall dfs if (it != parent): dfs(it, node, dp) # Add the size of the # subtree beneath it dp[node] += dp[it] # Function to assign weights to edges # to maximize the final sum def maximizeSum(a, n): # Initialize it which stores the # height of the subtree beneath it dp = [0 for i in range(n + 1)] # Call the DFS function to dfs(1, 0, dp) # Sort the given array a = sorted(a[:-1]) # Stores the number of times an # edge is part of a path ans = [] # Iterate for all edges and find the # number of nodes on the left and on the right for it in edges: if len(it) > 0: # Node 1 x = it[0] # Node 2 y = it[1] # If the number of nodes below is less # then the other will be n - dp[node] if (dp[x] < dp[y]): fi = dp[x] sec = n - dp[x] ans.append(fi * sec) # Second condition else: fi = dp[y] sec = n - dp[y] ans.append(fi * sec) # Sort the number of times # an edges occurs in the path ans = sorted(ans) res = 0 # Find the summation of all those # paths and return for i in range(n - 1): res += ans[i] * a[i] return res # Driver code n = 5 # Add an edge 1-2 in the tree addEdge(1, 2) # Add an edge 2-3 in the tree addEdge(1, 3) # Add an edge 3-4 in the tree addEdge(3, 4) # Add an edge 3-5 in the tree addEdge(3, 5) # Array which gives the edges weight # to be assigned a = [6, 3, 1, 9, 3] print(maximizeSum(a, n)) # This code is contributed by Mohit Kumar
Javascript
<script>
// JavaScript program to implement the
// above approach
let edges = new Array().fill(0).map(()=>new Array())
let tree = new Array(100).fill(0).map(()=>new Array())
// Function to add an edge to the tree
function addEdge(x, y){
edges.push([x, y])
tree[x].push(y)
tree[y].push(x)
}
// Function to run DFS and calculate the
// height of the subtree below it
function dfs(node, parent, dp){
// Initially initialize with 1
dp[node] = 1
// Traverse for all nodes connected to node
for(let it of tree[node]){
// If node is not parent
// then recall dfs
if (it != parent){
dfs(it, node, dp)
// Add the size of the
// subtree beneath it
dp[node] += dp[it]
}
}
}
// Function to assign weights to edges
// to maximize the final sum
function maximizeSum(a, n){
// Initialize it which stores the
// height of the subtree beneath it
let dp = new Array(n+1).fill(0)
// Call the DFS function to
dfs(1, 0, dp)
// Sort the given array
a = a.slice(0, n-1).sort().concat(a.slice(n-1,));
// Stores the number of times an
// edge is part of a path
let ans = []
// Iterate for all edges and find the
// number of nodes on the left and on the right
for(let it of edges){
if(it.length > 0){
// Node 1
let x = it[0]
// Node 2
let y = it[1]
// If the number of nodes below is less
// then the other will be n - dp[node]
if (dp[x] < dp[y]){
let fi = dp[x]
let sec = n - dp[x]
ans.push(fi * sec)
}
// Second condition
else{
let fi = dp[y]
let sec = n - dp[y]
ans.push(fi * sec)
}
}
}
// Sort the number of times
// an edges occurs in the path
ans.sort()
let res = 0
// Find the summation of all those
// paths and return
for(let i=0;i<n-1;i++)
res += ans[i] * a[i]
return res
}
// Driver code
let n = 5
// Add an edge 1-2 in the tree
addEdge(1, 2)
// Add an edge 2-3 in the tree
addEdge(1, 3)
// Add an edge 3-4 in the tree
addEdge(3, 4)
// Add an edge 3-5 in the tree
addEdge(3, 5)
// Array which gives the edges weight
// to be assigned
let a = [6, 3, 1, 9, 3]
document.write(maximizeSum(a, n),"</br>")
// This code is contributed by shinjanpatra
</script>
Producción:
94
Complejidad de tiempo: O(V+E) + O(n log n), para hacer los dfs y clasificar
Espacio auxiliar: O(n), ya que se utilizan espacios adicionales