# HackerRank Roads in HackerLand problem solution

In this HackerRank Roads in HackerLand problem solution we have given a map of HackerLand and we need to find the sum of the minimum distance between each pair of cities and we need to print the answer in binary representation.

## Problem solution in Python.

```#!/bin/python3

p = list(range(10 ** 5))

def dsu_get(v):
if p[v] != v: p[v] = dsu_get(p[v])

return p[v]

def dsu_merge(u, v):
u = dsu_get(u)
v = dsu_get(v)
p[u] = v

return u != v

n, m = map(int, input().split())
e = []
for i in range(m):
a, b, c = map(int, input().split())
e += [(c, b - 1, a - 1)]

e.sort()

G = [[] for x in range(n)]
for c, a, b in e:
if dsu_merge(a, b):
G[a] += [(b, c)]
G[b] += [(a, c)]

f = [0] * m
def dfs(v, par = -1):
sz = 1
for u, c in G[v]:
if u == par: continue

y = dfs(u, v)

f[c] = y * (n - y)
sz += y

return sz

dfs(0)

ans = 0
for x in f[::-1]:
ans *= 2
ans += x

print(bin(ans)[2:])
```

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

## Problem solution in Java.

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

public class Solution {
public static class Edge {
public int node1, node2, power;
long count;

public Edge(int node1, int node2, int power) {
this.node1 = node1;
this.node2 = node2;
this.power = power;
}
}

public static class Node {
public int id;

public ArrayList<Edge> edges;

public Node(int id) {
this.id = id;
edges = new ArrayList<>();
}
}

static long[] results;
static int N, M;
static Node[] nodes;

// disjoint set implementation
static int[] forests;

static int find(int node) {
if (forests[node] < 0) return node;
return forests[node] = find(forests[node]);
}

static void join(int root1, int root2) {
if (forests[root2] < forests[root1]) forests[root1] = root2;
else {
if (forests[root1] == forests[root2]) forests[root1]--;
forests[root2] = root1;
}
}

// count edge uses
static int descend(Node parent, Node node) {
int total = 1;

for (Edge edge : node.edges) {
if (parent != null && (edge.node1 == parent.id || edge.node2 == parent.id)) continue;

Node target;

if (edge.node1 == node.id) target = nodes[edge.node2];
else target = nodes[edge.node1];

edge.count = descend(node, target);

total += edge.count;
}

}

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);

N = scanner.nextInt();
M = scanner.nextInt();

Edge[] edges = new Edge[M];

results = new long[2 * M];

nodes = new Node[N];
for (int n = 0; n < N; n++) nodes[n] = new Node(n);

for (int m = 0; m < M; m++) {
int node1 = scanner.nextInt() - 1;
int node2 = scanner.nextInt() - 1;
int power = scanner.nextInt();
edges[power] = new Edge(node1, node2, power);
}

ArrayList<Edge> bucket = new ArrayList<>();

// build MST
forests = new int[N];
Arrays.fill(forests, -1);

for (int m = 0; m < M; m++) {
int n1 = edges[m].node1, n2 = edges[m].node2;
if (find(n1) != find(n2)) {
join(find(n1), find(n2));

}
}

// calculate distances
Node root = nodes[bucket.get(0).node1];

descend(null, root);

for (Edge edge : bucket) results[edge.power] = edge.count * (N - edge.count);

// binary output
long carry;
long nm;

long[] buffer = new long[2 * M];

for (int i = 0; i < 2 * M; i++) {
nm = results[i];
int j = 0;
while (nm != 0) {
buffer[i + j] += nm % 2;
nm /= 2;
j++;
}
}

carry = 0;
Arrays.fill(results, 0);
for (int i = 0; i < 2 * M; i++) {
results[i] = (buffer[i] + carry) % 2;
carry = (buffer[i] + carry) / 2;
}

boolean init = false;
for (int i = 2 * M - 1; i >= 0; i--) {
if (results[i] == 0 && init) System.out.print(0);
else if (results[i] == 1) {
System.out.print(1);
init = true;
}
}
}
}
```

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

## Problem solution in C++.

```#include <bits/stdc++.h>

using namespace std;

template<class T> inline T sqr(const T& a) {
return a * a;
}

template<class T> inline int len(const T &c) {
return static_cast<int>(c.size());
}

template<class T> inline void maximize(T &r, const T c) {
r = max(r, c);
}

template<class T> inline void minimize(T &r, const T c) {
r = min(r, c);
}

typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;

const ld EPS = 1e-9;
const ld PI = 2 * acos(0.0);
const int N = 100100;

struct DSU {
int size;
vector<int> p;
vector<int> w;

DSU(int n) :
size(n),
p(n, -1),
w(n, 1) {}

int Parent(int v) {
if (p[v] == -1)
return v;
return p[v] = Parent(p[v]);
}

void Union(int u, int v) {
u = Parent(u);
v = Parent(v);
if (w[u] < w[v])
swap(u, v);
p[v] = u;
w[u] += w[v];
}
};

vector<pt> g[N];
vector<pt> tree[N];
li total;
int subt[N];
vector<li> ans;

int Dfs(int v, int prev, int w) {
subt[v] = 1;
for (pt &e : tree[v]) {
if (e.first == prev)
continue;
subt[v] += Dfs(e.first, v, e.second);
}
if (w >= 0) {
li used = (total - subt[v]) * subt[v];
while (w >= len(ans)) {
ans.push_back(0);
}
ans[w] += used;
}
return subt[v];
}

int main() {
int n, m;
scanf("%d%d", &n, &m);
total = n;
vector<pair<int, pt>> edges;
for (int i = 0; i < m; ++i) {
int x, y, w;
scanf("%d%d%d", &x, &y, &w);
--x, --y;
edges.push_back({w, {x, y}});
g[x].push_back({y, w});
g[y].push_back({x, w});
}
sort(edges.begin(), edges.end());

DSU dsu(n);
for (auto &e : edges) {
int x = e.second.first;
int y = e.second.second;
int u = dsu.Parent(x);
int v = dsu.Parent(y);
if (u != v) {
tree[x].push_back({y, e.first});
tree[y].push_back({x, e.first});
dsu.Union(u, v);
}
}

Dfs(0, -1, -1);

li r = 0;
for (int i = 0; i < len(ans) || r; ++i) {
while (i >= len(ans)) {
ans.push_back(0);
}
r += ans[i];
ans[i] = r & 1;
r >>= 1;
}
bool started = false;
for (int i = len(ans) - 1; i >= 0; --i) {
bool on = ans[i] > 0;
if (on) {
started = true;
}
if (started) {
putchar(on ? '1' : '0');
}
}
if (!started) {
puts("0");
} else {
puts("");
}
return 0;
}
```

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

## Problem solution in C.

```#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <malloc.h>

typedef struct _node{
int vertex;
int weight;
struct _node * next;
}node;

typedef node * pnode;

pnode AL[200005];
int hsh[100005];
long long int ans[200105];

void insert(pnode *A,int v,int w){
pnode p=(pnode)malloc(sizeof(node));
p->vertex=v;
p->weight=w;
p->next=*A;
*A=p;
return;
}

int find(int i){
if(hsh[i]==i)return i;
hsh[i]=find(hsh[i]);
return hsh[i];
}

int check(int i,int j){
int hi=find(i),hj=find(j);
if(hi==hj)return 0;
if(hj<hi)hsh[hi]=hj;
else hsh[hj]=hi;
return 1;
}

int dfs(int i,int pre,int n){
pnode p=AL[i];
int count=1;
int temp;
while(p!=NULL){
if(p->vertex!=pre){
temp=dfs(p->vertex,i,n);
ans[p->weight]=(long long int)(n-temp)*(long long int)temp;
count+=temp;
}
p=p->next;
}
return count;
}

int main() {
int n,m,edge[200005][2],i,j,k,u,v,w,mx;
long long int longj;
scanf("%d%d",&n,&m);
for(i=0;i<m;i++){
scanf("%d%d%d",&u,&v,&w);
edge[w][0]=u-1;
edge[w][1]=v-1;
}
for(i=0;i<n;i++)hsh[i]=i;
for(i=0;i<n;i++)AL[i]=NULL;
for(i=j=0;i<m&&j<n-1;i++){
if(check(edge[i][0],edge[i][1])){
insert(&AL[edge[i][0]],edge[i][1],i);
insert(&AL[edge[i][1]],edge[i][0],i);
j++;
}
}
k=dfs(0,-1,n);
mx=m;
for(i=0;i<mx;i++){
longj=ans[i];
ans[i]=0;
k=0;
while(longj>0){
ans[i+k]+=longj%2;
k++;
longj/=2;
if(mx<i+k)mx=i+k;
}
}
i=mx;
while(i>0&&ans[i]==0)i--;
for(;i>=0;i--)printf("%lld",ans[i]);
return 0;
}
```

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