Dado un árbol ponderado no dirigido que tiene N Nodes y E aristas. Preguntas Q dadas , con cada consulta indicando un Node inicial. La tarea es imprimir la suma de las distancias desde un Node inicial dado S hasta cada Node hoja en el árbol ponderado.
Ejemplos:
Entrada: N = 5, E = 4, Q = 3
1
(4) / \ (2)
/ \
4 2
(5)/ \ (3)
/ \
5 3
Consulta 1:S = 1
Consulta 2: S = 3
Consulta 3: S = 5
Salida:
16
17
19
Explicación:
Los tres Nodes de hoja en el árbol son 3, 4 y 5.
Para S = 1, la suma de las distancias desde el Node 1 hasta los Nodes de hoja son: d(1, 4) + d(1, 3) + d(1, 5) = 4 + (2 + 5) + (2 + 3) = 16.
Para S = 3, la suma de las distancias del Node 3 a sus Nodes hoja son: d(3, 4) + d(3, 3) + d(3, 5) = (3 + 2 + 4) + 0 + (3 + 5) = 17
Para S = 5, la suma de las distancias del Node 5 a sus Nodes hoja son: d(5, 4) + d(5, 3) + d(5, 5) = (5 + 2 + 4) + (5 + 3) + 0 = 19Entrada: N = 3, E = 2, Q = 2
1
(9) / \ (1)
/ \
2 3
Consulta 1:S = 1
Consulta 2: S = 2
Consulta 3: S = 3
Salida:
10
10
10
Enfoque ingenuo:
para cada consulta, recorra todo el árbol y encuentre la suma de la distancia desde el Node de origen dado hasta todos los Nodes de hoja.
Complejidad temporal: O(Q * N)
Enfoque eficiente: la idea es usar un cálculo previo de la suma de la distancia de cada Node a todos los Nodes hoja usando el algoritmo de programación dinámica en árboles y obtener la respuesta para cada consulta en tiempo constante.
Siga los pasos a continuación para resolver el problema
- Inicialice un vector dp para almacenar la suma de las distancias desde cada Node i a todos los Nodes hoja del árbol.
- Inicialice un vector de hojas para almacenar el recuento de los Nodes hoja en el subárbol del Node i considerando 1 como el Node raíz.
- Encuentre la suma de las distancias desde el Node i hasta todos los Nodes hoja en el subárbol de i considerando 1 como el Node raíz utilizando un algoritmo de búsqueda primero en profundidad modificado.
Sea el Node a el padre del Node i
- hojas[a] += hojas[i] ;
- dp[a] += dp[i] + hojas[i] * peso del borde entre Nodes(a, i) ;
- Utilice la técnica de reenraizamiento para encontrar la distancia de las hojas restantes del árbol que no están en el subárbol del Node i . Para calcular estas distancias, utilice otro algoritmo de búsqueda en profundidad primero (DFS) modificado para buscar y sumar la suma de las distancias de los Nodes hoja al Node i .
Sea a el Node padre e i el Node hijo, luego sea L
el número de Nodes hoja fuera del subárbol i que están presentes en el subárbol a
- L= hojas[a] – hojas[i] ;
- dp[i] += ( dp[a] – dp[i] ) + ( peso del borde entre Nodes(a, i) ) * ( L – hojas[i] ) ;
- hojas[i] += L ;
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above problem
#include <bits/stdc++.h>
using namespace std;
// MAX size
const int N = 1e5 + 5;
// graph with {destination, weight};
vector<vector<pair<int, int> > > v(N);
// for storing the sum for ith node
vector<int> dp(N);
// leaves in subtree of ith.
vector<int> leaves(N);
int n;
// dfs to find sum of distance
// of leaves in the
// subtree of a node
void dfs(int a, int par)
{
// flag is the node is
// leaf or not;
bool leaf = 1;
for (auto& i : v[a]) {
// skipping if parent
if (i.first == par)
continue;
// setting flag to false
leaf = 0;
// doing dfs call
dfs(i.first, a);
}
// doing calculation
// in postorder.
if (leaf == 1) {
// if the node is leaf then
// we just increment
// the no. of leaves under
// the subtree of a node
leaves[a] += 1;
}
else {
for (auto& i : v[a]) {
if (i.first == par)
continue;
// adding num of leaves
leaves[a]
+= leaves[i.first];
// calculating answer for
// the sum in the subtree
dp[a] = dp[a]
+ dp[i.first]
+ leaves[i.first]
* i.second;
}
}
}
// dfs function to find the
// sum of distance of leaves
// outside the subtree
void dfs2(int a, int par)
{
for (auto& i : v[a]) {
if (i.first == par)
continue;
// number of leaves other
// than the leaves in the
// subtree of i
int leafOutside = leaves[a] - leaves[i.first];
// adding the contribution
// of leaves outside to
// the ith node
dp[i.first] += (dp[a] - dp[i.first]);
dp[i.first] += i.second
* (leafOutside
- leaves[i.first]);
// adding the leafs outside
// to ith node's leaves.
leaves[i.first]
+= leafOutside;
dfs2(i.first, a);
}
}
void answerQueries(
vector<int> queries)
{
// calculating the sum of
// distance of leaves in the
// subtree of a node assuming
// the root of the tree is 1
dfs(1, 0);
// calculating the sum of
// distance of leaves outside
// the subtree of node
// assuming the root of the
// tree is 1
dfs2(1, 0);
// answering the queries;
for (int i = 0;
i < queries.size(); i++) {
cout << dp[queries[i]] << endl;
}
}
// Driver Code
int main()
{
// Driver Code
/*
1
(4) / \ (2)
/ \
4 2
(5)/ \ (3)
/ \
5 3
*/
n = 5;
// initialising tree
v[1].push_back(
make_pair(4, 4));
v[4].push_back(
make_pair(1, 4));
v[1].push_back(
make_pair(2, 2));
v[2].push_back(
make_pair(1, 2));
v[2].push_back(
make_pair(3, 3));
v[3].push_back(
make_pair(2, 3));
v[2].push_back(
make_pair(5, 5));
v[5].push_back(
make_pair(2, 5));
vector<int>
queries = { 1, 3, 5 };
answerQueries(queries);
}
Java
// Java program for the above problem
import java.util.*;
import java.lang.*;
class GFG{
static class pair
{
int first, second;
pair(int f, int s)
{
this.first = f;
this.second = s;
}
}
// MAX size
static final int N = (int)1e5 + 5;
// Graph with {destination, weight};
static ArrayList<ArrayList<pair>> v;
// For storing the sum for ith node
static int[] dp = new int[N];
// Leaves in subtree of ith.
static int[] leaves = new int[N];
static int n;
// dfs to find sum of distance
// of leaves in the subtree of
// a node
static void dfs(int a, int par)
{
// Flag is the node is
// leaf or not;
int leaf = 1;
for(pair i : v.get(a))
{
// Skipping if parent
if (i.first == par)
continue;
// Setting flag to false
leaf = 0;
// Doing dfs call
dfs(i.first, a);
}
// Doing calculation
// in postorder.
if (leaf == 1)
{
// If the node is leaf then
// we just increment the
// no. of leaves under
// the subtree of a node
leaves[a] += 1;
}
else
{
for(pair i : v.get(a))
{
if (i.first == par)
continue;
// Adding num of leaves
leaves[a] += leaves[i.first];
// Calculating answer for
// the sum in the subtree
dp[a] = dp[a] + dp[i.first] +
leaves[i.first] *
i.second;
}
}
}
// dfs function to find the
// sum of distance of leaves
// outside the subtree
static void dfs2(int a, int par)
{
for(pair i : v.get(a))
{
if (i.first == par)
continue;
// Number of leaves other
// than the leaves in the
// subtree of i
int leafOutside = leaves[a] -
leaves[i.first];
// Adding the contribution
// of leaves outside to
// the ith node
dp[i.first] += (dp[a] - dp[i.first]);
dp[i.first] += i.second *
(leafOutside -
leaves[i.first]);
// Adding the leafs outside
// to ith node's leaves.
leaves[i.first] += leafOutside;
dfs2(i.first, a);
}
}
static void answerQueries(int[] queries)
{
// Calculating the sum of
// distance of leaves in the
// subtree of a node assuming
// the root of the tree is 1
dfs(1, 0);
// Calculating the sum of
// distance of leaves outside
// the subtree of node
// assuming the root of the
// tree is 1
dfs2(1, 0);
// Answering the queries;
for(int i = 0; i < queries.length; i++)
{
System.out.println(dp[queries[i]]);
}
}
// Driver code
public static void main(String[] args)
{
/*
1
(4) / \ (2)
/ \
4 2
(5)/ \ (3)
/ \
5 3
*/
n = 5;
v = new ArrayList<>();
for(int i = 0; i <= n; i++)
v.add(new ArrayList<pair>());
// Initialising tree
v.get(1).add(new pair(4, 4));
v.get(4).add(new pair(1, 4));
v.get(1).add(new pair(2, 2));
v.get(2).add(new pair(1, 2));
v.get(2).add(new pair(3, 3));
v.get(3).add(new pair(2, 3));
v.get(2).add(new pair(5, 5));
v.get(5).add(new pair(2, 5));
// System.out.println(v);
int[] queries = { 1, 3, 5 };
answerQueries(queries);
}
}
// This code is contributed by offbeat
Python3
# Python3 program for the above problem
# MAX size
N = 10 ** 5 + 5
# Graph with {destination, weight}
v = [[] for i in range(N)]
# For storing the sum for ith node
dp = [0] * N
# Leaves in subtree of ith.
leaves = [0] * (N)
n = 0
# dfs to find sum of distance
# of leaves in the subtree of
# a node
def dfs(a, par):
# flag is the node is
# leaf or not
leaf = 1
for i in v[a]:
# Skipping if parent
if (i[0] == par):
continue
# Setting flag to false
leaf = 0
# Doing dfs call
dfs(i[0], a)
# Doing calculation
# in postorder.
if (leaf == 1):
# If the node is leaf then
# we just increment
# the no. of leaves under
# the subtree of a node
leaves[a] += 1
else:
for i in v[a]:
if (i[0] == par):
continue
# Adding num of leaves
leaves[a] += leaves[i[0]]
# Calculating answer for
# the sum in the subtree
dp[a] = (dp[a] + dp[i[0]] +
leaves[i[0]] * i[1])
# dfs function to find the
# sum of distance of leaves
# outside the subtree
def dfs2(a, par):
for i in v[a]:
if (i[0] == par):
continue
# Number of leaves other
# than the leaves in the
# subtree of i
leafOutside = leaves[a] - leaves[i[0]]
# Adding the contribution
# of leaves outside to
# the ith node
dp[i[0]] += (dp[a] - dp[i[0]])
dp[i[0]] += i[1] * (leafOutside -
leaves[i[0]])
# Adding the leafs outside
# to ith node's leaves.
leaves[i[0]] += leafOutside
dfs2(i[0], a)
def answerQueries(queries):
# Calculating the sum of
# distance of leaves in the
# subtree of a node assuming
# the root of the tree is 1
dfs(1, 0)
# Calculating the sum of
# distance of leaves outside
# the subtree of node
# assuming the root of the
# tree is 1
dfs2(1, 0)
# Answering the queries
for i in range(len(queries)):
print(dp[queries[i]])
# Driver Code
if __name__ == '__main__':
# 1
# (4) / \ (2)
# / \
# 4 2
# (5)/ \ (3)
# / \
# 5 3
#
n = 5
# Initialising tree
v[1].append([4, 4])
v[4].append([1, 4])
v[1].append([2, 2])
v[2].append([1, 2])
v[2].append([3, 3])
v[3].append([2, 3])
v[2].append([5, 5])
v[5].append([2, 5])
queries = [ 1, 3, 5 ]
answerQueries(queries)
# This code is contributed by mohit kumar 29
C#
// C# program for the above problem
using System;
using System.Collections.Generic;
class GFG {
// MAX size
static int N = 100005;
// Graph with {destination, weight}
static List<List<Tuple<int,int>>> v = new List<List<Tuple<int,int>>>();
// For storing the sum for ith node
static int[] dp = new int[N];
// Leaves in subtree of ith.
static int[] leaves = new int[N];
// dfs to find sum of distance
// of leaves in the subtree of
// a node
static void dfs(int a, int par)
{
// flag is the node is
// leaf or not
bool leaf = true;
foreach(Tuple<int,int> i in v[a])
{
// Skipping if parent
if (i.Item1 == par)
continue;
// Setting flag to false
leaf = false;
// Doing dfs call
dfs(i.Item1, a);
}
// Doing calculation
// in postorder.
if (leaf == true)
{
// If the node is leaf then
// we just increment
// the no. of leaves under
// the subtree of a node
leaves[a] += 1;
}
else
{
foreach(Tuple<int,int> i in v[a])
{
if (i.Item1 == par)
continue;
// Adding num of leaves
leaves[a] += leaves[i.Item1];
// Calculating answer for
// the sum in the subtree
dp[a] = (dp[a] + dp[i.Item1] + leaves[i.Item1] * i.Item2);
}
}
}
// dfs function to find the
// sum of distance of leaves
// outside the subtree
static void dfs2(int a, int par)
{
foreach(Tuple<int,int> i in v[a])
{
if (i.Item1 == par)
continue;
// Number of leaves other
// than the leaves in the
// subtree of i
int leafOutside = leaves[a] - leaves[i.Item1];
// Adding the contribution
// of leaves outside to
// the ith node
dp[i.Item1] += (dp[a] - dp[i.Item1]);
dp[i.Item1] += i.Item2 * (leafOutside - leaves[i.Item1]);
// Adding the leafs outside
// to ith node's leaves.
leaves[i.Item1] += leafOutside;
dfs2(i.Item1, a);
}
}
static void answerQueries(List<int> queries)
{
// Calculating the sum of
// distance of leaves in the
// subtree of a node assuming
// the root of the tree is 1
dfs(1, 0);
// Calculating the sum of
// distance of leaves outside
// the subtree of node
// assuming the root of the
// tree is 1
dfs2(1, 0);
// Answering the queries
for(int i = 0; i < queries.Count; i++)
Console.WriteLine(dp[queries[i]]);
}
static void Main() {
// Driver Code
/*
1
(4) / \ (2)
/ \
4 2
(5)/ \ (3)
/ \
5 3
*/
for(int i = 0; i < N; i++)
{
v.Add(new List<Tuple<int,int>>());
}
// initialising tree
v[1].Add(new Tuple<int,int>(4,4));
v[4].Add(new Tuple<int,int>(1,4));
v[1].Add(new Tuple<int,int>(2,2));
v[2].Add(new Tuple<int,int>(1,2));
v[2].Add(new Tuple<int,int>(3,3));
v[3].Add(new Tuple<int,int>(2,3));
v[2].Add(new Tuple<int,int>(5,5));
v[5].Add(new Tuple<int,int>(2,5));
List<int> queries = new List<int>{ 1, 3, 5 };
answerQueries(queries);
}
}
// This code is contributed by suresh07.
Javascript
<script>
// JavaScript program for the above problem
class pair
{
constructor(f,s)
{
this.first = f;
this.second = s;
}
}
// MAX size
let N = 1e5 + 5;
// Graph with {destination, weight};
let v=[];
// For storing the sum for ith node
let dp = new Array(N);
// Leaves in subtree of ith.
let leaves = new Array(N);
for(let i=0;i<N;i++)
{
dp[i]=0;
leaves[i]=0;
}
let n;
// dfs to find sum of distance
// of leaves in the subtree of
// a node
function dfs(a,par)
{
// Flag is the node is
// leaf or not;
let leaf = 1;
for(let i=0;i<v[a].length;i++)
{
// Skipping if parent
if (v[a][i].first == par)
continue;
// Setting flag to false
leaf = 0;
// Doing dfs call
dfs(v[a][i].first, a);
}
// Doing calculation
// in postorder.
if (leaf == 1)
{
// If the node is leaf then
// we just increment the
// no. of leaves under
// the subtree of a node
leaves[a] += 1;
}
else
{
for(let i=0;i<v[a].length;i++)
{
if (v[a][i].first == par)
continue;
// Adding num of leaves
leaves[a] += leaves[v[a][i].first];
// Calculating answer for
// the sum in the subtree
dp[a] = dp[a] + dp[v[a][i].first] +
leaves[v[a][i].first] *
v[a][i].second;
}
}
}
// dfs function to find the
// sum of distance of leaves
// outside the subtree
function dfs2(a,par)
{
for(let i=0;i< v[a].length;i++)
{
if (v[a][i].first == par)
continue;
// Number of leaves other
// than the leaves in the
// subtree of i
let leafOutside = leaves[a] -
leaves[v[a][i].first];
// Adding the contribution
// of leaves outside to
// the ith node
dp[v[a][i].first] += (dp[a] - dp[v[a][i].first]);
dp[v[a][i].first] += v[a][i].second *
(leafOutside -
leaves[v[a][i].first]);
// Adding the leafs outside
// to ith node's leaves.
leaves[v[a][i].first] += leafOutside;
dfs2(v[a][i].first, a);
}
}
function answerQueries(queries)
{
// Calculating the sum of
// distance of leaves in the
// subtree of a node assuming
// the root of the tree is 1
dfs(1, 0);
// Calculating the sum of
// distance of leaves outside
// the subtree of node
// assuming the root of the
// tree is 1
dfs2(1, 0);
// Answering the queries;
for(let i = 0; i < queries.length; i++)
{
document.write(dp[queries[i]]+"<br>");
}
}
// Driver code
/*
1
(4) / \ (2)
/ \
4 2
(5)/ \ (3)
/ \
5 3
*/
n = 5;
v = [];
for(let i = 0; i <= n; i++)
v.push([]);
// Initialising tree
v[1].push(new pair(4, 4));
v[4].push(new pair(1, 4));
v[1].push(new pair(2, 2));
v[2].push(new pair(1, 2));
v[2].push(new pair(3, 3));
v[3].push(new pair(2, 3));
v[2].push(new pair(5, 5));
v[5].push(new pair(2, 5));
// System.out.println(v);
let queries = [ 1, 3, 5 ];
answerQueries(queries);
// This code is contributed by patel2127
</script>
Producción:
16 17 19
Complejidad temporal: O(N + Q)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por insiderpants y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA