Given a Undirected Weighted Tree having N nodes and E edges. Given Q queries, with each query indicating a starting node. The task is to print the sum of the distances from a given starting node S to every leaf node in the Weighted Tree.
Examples:
Input: N = 5, E = 4, Q = 3
1
(4) / \ (2)
/ \
4 2
(5)/ \ (3)
/ \
5 3
Query 1: S = 1
Query 2: S = 3
Query 3: S = 5
Output :
16
17
19
Explanation :
The three leaf nodes in the tree are 3, 4 and 5.
For S = 1, the sum of the distances from node 1 to the leaf nodes are: d(1, 4) + d(1, 3) + d(1, 5) = 4 + (2 + 5) + (2 + 3) = 16.
For S = 3, the sum of the distances from node 3 to its leaf nodes are: d(3, 4) + d(3, 3) + d(3, 5) = (3 + 2 + 4) + 0 + (3 + 5) = 17
For S = 5, the sum of the distances from node 5 to its leaf nodes are: d(5, 4) + d(5, 3) + d(5, 5) = (5 + 2 + 4) + (5 + 3) + 0 = 19Input: N = 3, E = 2, Q = 2
1
(9) / \ (1)
/ \
2 3
Query 1: S = 1
Query 2: S = 2
Query 3: S = 3
Output :
10
10
10
Naive Approach:
For each query, traverse the entire tree and find the sum of the distance from the given source node to all the leaf nodes.
Time Complexity: O(Q * N)
Efficient Approach: The idea is to use pre-compute the sum of the distance of every node to all the leaf nodes using Dynamic Programming on trees Algorithm and obtain the answer for each query in constant time.
Follow the steps below to solve the problem
- Initialize a vector dp to store the sum of the distances from each node i to all the leaf nodes of the tree.
- Initialize a vector leaves to store the count of the leaf nodes in the sub-tree of node i considering 1 as the root node.
- Find the sum of the distances from node i to all the leaf nodes in the sub-tree of i considering 1 as the root node using a modified Depth First Search Algorithm.
Let node a be the parent of node i
- leaves[a] += leaves[i] ;
- dp[a] += dp[i] + leaves[i] * weight of edge between nodes(a, i) ;
- Use the re-rooting technique to find the distance of the remaining leaves of the tree that are not in the sub-tree of node i. To calculate these distances, use another modified Depth First Search (DFS) algorithm to find and add the sum of the distances of leaf nodes to node i.
Let a be the parent node and i be the child node, then
Let the number of leaf nodes outside the sub-tree i that are present in the sub-tree a be L
- L = leaves[a] – leaves[i] ;
- dp[i] += ( dp[a] – dp[i] ) + ( weight of edge between nodes(a, i) ) * ( L – leaves[i] ) ;
- leaves[i] += L ;
Below is the implementation of the above approach:
C++
// C++ program for the above problem#include <bits/stdc++.h>using namespace std;// MAX sizeconst int N = 1e5 + 5;// graph with {destination, weight};vector<vector<pair<int, int> > > v(N);// for storing the sum for ith nodevector<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 nodevoid 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 subtreevoid 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 leaves 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 Codeint 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 problemimport 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 sizestatic final int N = (int)1e5 + 5; // Graph with {destination, weight};static ArrayList<ArrayList<pair>> v; // For storing the sum for ith nodestatic 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 nodestatic 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 subtreestatic 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 leaves 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 codepublic 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 sizeN = 10 ** 5 + 5# Graph with {destination, weight}v = [[] for i in range(N)]# For storing the sum for ith nodedp = [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 nodedef 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 subtreedef 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 leaves 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 Codeif __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 problemusing 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 leaves 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 problemclass pair{ constructor(f,s) { this.first = f; this.second = s; }}// MAX sizelet N = 1e5 + 5;// Graph with {destination, weight};let v=[];// For storing the sum for ith nodelet 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 nodefunction 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 subtreefunction 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 leaves 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 treev[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> |
Output:
16 17 19
Time Complexity: O(N + Q)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
