# HackerRank Tree Flow problem solution

In this HackerRank Tree Flow problem solution, we have an undirected connected acyclic graph and we have a weighted tree with n vertices. we need to calculate and print the maximum total value of A for a given tree T.

## Problem solution in Python.

```from collections import defaultdict
from sys import stdin, stdout
from heapq import heappop, heappush

def dijkstra(n, graph, u):
distance = [float("inf")] * (n + 1)
distance[u] = 0
visited = [False] * (n + 1)
visited[u] = True
queue = [(distance[u], u)]
while queue:
d, u = heappop(queue)
for v, w in graph[u]:
if not visited[v] and distance[v] > d + w:
visited[v] = True
distance[v] = d + w
heappush(queue, (distance[v], v))
return distance[1:]

def treeFlow(n, tree):
graph = defaultdict(list)
for u, v, w in tree:
graph[u].append((v, w))
graph[v].append((u, w))
return min(sum(dijkstra(n, graph, 1)), sum(dijkstra(n, graph, n)))

if __name__ == '__main__':
tree = [list(map(int, stdin.readline().rstrip().split())) for _ in range(n - 1)]
result = treeFlow(n, tree)
stdout.write(str(result) + '\n')
```

{"mode":"full","isActive":false}

## Problem solution in Java.

```import java.io.*;
import java.util.*;

public class Solution {
private static PrintWriter out;

static class Edge {
public int to;
public long weight;
public Edge(int to, int weight) {
this.to = to;
this.weight = weight;
}
}

public static void dfs(int node, int par, long cdist) {
dist[node] = cdist;
for (Edge e : graph[node]) {
if (e.to == par) continue;
dfs(e.to, node, cdist+e.weight);
}
}

public static void bfs(int node) {
int front = 0, back = 0;
Arrays.fill(vis, false);
queue[back++] = node;
dist[node] = 0;
vis[node] = true;
while (front < back) {
int cur = queue[front++];
for (Edge e : graph[cur]) {
if (vis[e.to]) continue;
vis[e.to] = true;
dist[e.to] = dist[cur] + e.weight;
queue[back++] = e.to;
}
}
}

public static ArrayList<Edge>[] graph;
public static long[] dist;
public static int[] queue;
public static boolean[] vis;
public static void main(String[] args) throws IOException {
out = new PrintWriter(System.out, true);

int n = in.nextInt();
graph = new ArrayList[n];
queue = new int[graph.length];
vis = new boolean[graph.length];
for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
for (int i = 0; i < n-1; i++) {
int a = in.nextInt()-1, b = in.nextInt()-1, c = in.nextInt();
}

dist = new long[n];
bfs(0);
long ans1 = 0;
for (int i = 0; i < n; i++) ans1 += dist[i];
bfs(n-1);
long ans2 = 0;
for (int i = 0; i < n; i++) ans2 += dist[i];
out.println(Math.min(ans1, ans2));
out.close();
System.exit(0);
}

public StringTokenizer tokenizer;

tokenizer = null;
}

public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
} catch (IOException e) {
throw new RuntimeException(e);
}
}
}

public int nextInt() {
return Integer.parseInt(next());
}
}

}```

{"mode":"full","isActive":false}

## Problem solution in C++.

```#include <iostream>
#include <cstdio>
#include <string.h>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <sstream>
#include <cmath>
#include <ctime>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector< vector<int> > vvi;
typedef vector<ll> vl;
typedef vector< vector<ll> > vvl;

#define forn(i, n) for (int i = 0; i < (int)(n); i++)
#define forv(i, v) forn(i, v.size())
#define all(v) v.begin(), v.end()
#define mp make_pair
#define pb push_back

struct Edge {
int v, w;
Edge() {}
Edge(int v, int w) : v(v), w(w) {}
};

vector< vector<Edge> > g;
vl d;

void dfs(int v, int p) {
for (Edge& e : g[v]) {
if (e.v == p) continue;
d[e.v] = d[v] + e.w;
dfs(e.v, v);
}
}

int main() {
#ifdef NEREVAR_PROJECT
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int n; cin >> n;
g = vector< vector<Edge> >(n);
forn(i, n - 1) {
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
a--, b--;
g[a].pb(Edge(b, c));
g[b].pb(Edge(a, c));
}
d = vl(n, 0);
dfs(0, -1);
ll s0 = 0;
forn(i, n) s0 += d[i];
d = vl(n, 0);
dfs(n - 1, -1);
ll s1 = 0;
forn(i, n) s1 += d[i];
cout << min(s0, s1) << endl;
return 0;
}
```

{"mode":"full","isActive":false}

## Problem solution in C.

```#include<stdio.h>
#include<stdlib.h>
typedef struct _lnode
{
int x;
int w;
struct _lnode *next;
}lnode;
lnode *table[500000];
void dfs(int x, int y, long long len, long long *ans)
{
lnode *p;
*ans += len;
for( p = table[x] ; p ; p = p -> next )
{
if( p -> x != y )
{
dfs(p -> x, x, len+p -> w, ans);
}
}
return;
}
void insert_edge(int x, int y, int w)
{
lnode *t = malloc(sizeof(lnode));
t -> x = y;
t -> w = w;
t -> next = table[x];
table[x] = t;
t = malloc(sizeof(lnode));
t -> x = x;
t -> w = w;
t -> next = table[y];
table[y] = t;
return;
}
int main()
{
int N, x, y, z, i;
long long ans1, ans2;
scanf("%d", &N);
for( i = ans1 = ans2 = 0 ; i < N - 1 ; i++ )
{
scanf("%d%d%d", &x, &y, &z);
insert_edge(x-1, y-1, z);
}
dfs(0, -1, 0, &ans1);
dfs(N-1, -1, 0, &ans2);
if( ans2 < ans1 )
{
ans1 = ans2;
}
printf("%lld", ans1);
return 0;
}
```

{"mode":"full","isActive":false}