# HackerRank Journey Scheduling problem solution

In this HackerRank Journey Scheduling problem solution, Fedya has prepared a list of M possible journeys. Each one is characterized by two integers - the starting city V and the total number of cities to be visited, K. For each of them, he is keen to know the total distance traveled by him.

## Problem solution in Python.

```#!/bin/python3

import math
import os
import random
import re
import sys
sys.setrecursionlimit(10**9)

#
# Complete the 'journeyScheduling' function below.
#
# The function is expected to return an INTEGER_ARRAY.
# The function accepts following parameters:
#  1. INTEGER n
#  3. 2D_INTEGER_ARRAY journeys
#

adj_list = [[] for i in range(n+1)]

start = 1
down_max_one = [(0, None)] * (n+1)
down_max_two = [0] * (n+1)
visited = [False] * (n+1)
queue = [(start, None)]

while len(queue):
edge = queue.pop()
u, p = edge
if not visited[u]:
queue.append(edge)
visited[u] = True
if visited[v]:
continue
# dfs_down(v)
queue.append((v, u))

continue

d_one = 0
nl_one = None
d_two = 0
nl_two = None
if v == p:
continue
d_v_one, nl_v_one = down_max_one[v]
d_v_one += 1
if d_v_one > d_one:
d_two = d_one
# nl_two = nl_one
d_one = d_v_one
nl_one = v

elif d_v_one >= d_two:
d_two = d_v_one
# nl_two = v

down_max_one[u] = (d_one, nl_one)
down_max_two[u] = d_two

# dfs_down(start)

visited = [False] * (n+1)
up_max = [0] * (n+1)
dist_max = [0] * (n+1)
queue = [(start, None)]

while len(queue):
edge = queue.pop()
u, p = edge
visited[u] = True

if p is None:
up_u = 0
# up_nl_u = None#set()
else:
up_p = up_max[p]
up_u_p = up_p + 1
d_p_one, d_nl_p_one = down_max_one[p]
d_p_two = down_max_two[p]

if u != d_nl_p_one:
d_p_v = d_p_one + 1
else:
d_p_v = d_p_two + 1

up_u = max(up_u_p, d_p_v)

up_max[u] = up_u
d_u, d_nl_u = down_max_one[u]

dist_max[u] = max(d_u, up_u)

if visited[v]:
continue
queue.append((v, u))

# dfs_max_dist(start, None)
diameter = max(dist_max)

# print(diameter)
# print(dist_max)
m = len(journeys)
res = [0] * m
for i in range(m) :
v, k = journeys[i]
max_v = dist_max[v]
res[i] = max_v + (k-1)*diameter
return res

if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')

first_multiple_input = input().rstrip().split()

n = int(first_multiple_input[0])

m = int(first_multiple_input[1])

roads = [[] for i in range(n-1)]

for i in range(n - 1):

journeys = [[] for i in range(m)]

for j in range(m):
journey_inputs = input().rstrip().split()
journeys[j] = (int(journey_inputs[0]), int(journey_inputs[1]))

# result = [0, 11]
fptr.write('\n'.join(map(str, result)))
fptr.write('\n')

fptr.close()
```

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

## Problem solution in Java.

```import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;

public class Solution {
private static class Node {
final int index;
final Set<Node> neighbors = new HashSet<>();

Node(int index) {
this.index = index;
}
}

/*
* Complete the journeyScheduling function below.
*/
static long[] journeyScheduling(int n, int[][] roads, int[][] journeys) {
Node[] nodes = new Node[n];
for (int i = 0; i < n; i++) {
nodes[i] = new Node(i);
}
}

Node start = findEnd(nodes[0]);
Node end = findEnd(start);
List<Node> diameterPath = findPath(start, end);
int diameter = diameterPath.size() - 1;
int[] distances = new int[n];
if ((diameter & 1) == 0) {
maxDistances(diameterPath.get(diameter/2), null, diameter/2, distances);
} else {
maxDistances(diameterPath.get(diameter/2), diameterPath.get(diameter/2 + 1), diameter/2 + 1, distances);
maxDistances(diameterPath.get(diameter/2 + 1), diameterPath.get(diameter/2), diameter/2 + 1, distances);
}
//        System.out.println(String.format("Diameter: %d, distances: %s", diameter, Arrays.toString(distances)));

long[] results = new long[journeys.length];
for (int i = 0; i < journeys.length; i++) {
results[i] = distances[journeys[i][0] - 1] + ((long) diameter)*(journeys[i][1] - 1);
}
return results;
}

private static class State {
final Node cur;
final Node prev;
final Iterator<Node> children;
final int distance;

State(Node cur, Node prev, int distance) {
this.cur = cur;
this.prev = prev;
this.children = cur.neighbors.iterator();
this.distance = distance;
}
}

private static Node findEnd(Node cur) {
Node end = cur;
int maxDistance = -1;
Deque<State> stack = new ArrayDeque<>();
while (!stack.isEmpty()) {
State state = stack.peekFirst();
if (state.children.hasNext()) {
Node child = state.children.next();
if (child == state.prev) {
// Do nothing
} else if (child.neighbors.size() == 1) {
if (state.distance > maxDistance) {
maxDistance = state.distance;
end = child;
}
} else {
stack.addFirst(new State(child, state.cur, state.distance + 1));
}
} else {
stack.removeFirst();
}
}
return end;
}

private static List<Node> findPath(Node cur, Node goal) {
Deque<State> stack = new ArrayDeque<>();
while (stack.peekFirst().cur != goal) {
State state = stack.peekFirst();
if (state.children.hasNext()) {
Node child = state.children.next();
if (child != state.prev) {
}
} else {
stack.removeFirst();
}
}

List<Node> path = new ArrayList<>();
while (!stack.isEmpty()) {
}
return path;
}

private static void maxDistances(Node cur, Node prev, int distance, int[] distances) {
distances[cur.index] = distance;
Deque<State> stack = new ArrayDeque<>();
while (!stack.isEmpty()) {
State state = stack.peekFirst();
if (state.children.hasNext()) {
Node child = state.children.next();
if (child != state.prev) {
distances[child.index] = state.distance + 1;
stack.addFirst(new State(child, state.cur, state.distance + 1));
}
} else {
stack.removeFirst();
}
}
}

private static final Scanner scanner = new Scanner(System.in);

public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

String[] nm = scanner.nextLine().split(" ");
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])*");

int n = Integer.parseInt(nm[0]);

int m = Integer.parseInt(nm[1]);

scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])*");

}
}

int[][] journeys = new int[m][2];

for (int journeysRowItr = 0; journeysRowItr < m; journeysRowItr++) {
String[] journeysRowItems = scanner.nextLine().split(" ");
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])*");

for (int journeysColumnItr = 0; journeysColumnItr < 2; journeysColumnItr++) {
int journeysItem = Integer.parseInt(journeysRowItems[journeysColumnItr]);
journeys[journeysRowItr][journeysColumnItr] = journeysItem;
}
}

long[] result;
//        try {
/*        } catch (StackOverflowError e) {
result = new long[1];
}*/

for (int resultItr = 0; resultItr < result.length; resultItr++) {
bufferedWriter.write(String.valueOf(result[resultItr]));

if (resultItr != result.length - 1) {
bufferedWriter.write("\n");
}
}

bufferedWriter.newLine();

bufferedWriter.close();

scanner.close();
}
}
```

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

## Problem solution in C++.

```#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

vector<int> visit;
int len;

int dfs(vector<map<int, int> >& g, int node, int dist) {
//cout << "dfs " << node << " dist " << dist << endl;
visit[node] = 1;
int max1 = dist, max2 = 0, max_dep = 0;
for(auto iter = g[node].begin(); iter != g[node].end(); ++iter) {
if(iter->second >= max1) {
max2 = max1;
max1 = iter->second;
} else {
max2 = max(iter->second, max2);
}
}
//cout << "nod " << node << " max " << max1 << " " << max2 << endl;
for(auto iter = g[node].begin(); iter != g[node].end(); ++iter) {
if(visit[iter->first]) {
iter->second = dist;
} else {
iter->second = dfs(g, iter->first, 1 + (iter->second != max1 ? max1 : max2));
max_dep = max(max_dep, iter->second);
}
}
for(auto it2 = g[node].begin(); it2 != g[node].end(); ++it2) {
//cout << "(" << it2->first << ", " <<it2->second << ") ";
}
//cout << endl << len << endl;
len = max(len, dist);
return max_dep + 1;
}

int main() {
int n, m;
cin >> n >> m;
vector<map<int, int> > g(n);
for(int i = 0; i < n - 1; ++i) {
int a, b;
cin >> a >> b;
g[a - 1][b - 1] = 0;
g[b - 1][a - 1] = 0;
}
visit.assign(n, 0);
dfs(g, 0, 0);
visit.assign(n, 0);
dfs(g, 0, 0);
/*
for(auto it1 = g.begin(); it1 != g.end(); ++it1) {
for(auto it2 = (*it1).begin(); it2 != (*it1).end(); ++it2) {
cout << "(" << it2->first << ", " <<it2->second << ") ";
}
cout << endl;
}*/

//cout << "len " << len << endl;

while(m--) {
int v, dist = 0;
long long k, sum = 0;
cin >> v >> k;
for(auto iter = g[v - 1].begin(); iter != g[v - 1].end(); ++iter) {
dist = max(dist, iter->second);
}
sum = dist + (k - 1) * len;
cout << sum << endl;
}
return 0;
}
```

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

## Problem solution in C.

```#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct _node{
int x;
int w;
struct _node *next;
} lnode;
void insert_edge(int x,int y,int w);
void dfs1(int x);
void dfs2(int x,int y);
int max(int x,int y);
int h[100000],sh[100000],l[100000],u[100000],trace[100000];
lnode *table[100000]={0};

int main(){
int N,M,x,y,i;
scanf("%d%d",&N,&M);
for(i=0;i<N-1;i++){
scanf("%d%d",&x,&y);
insert_edge(x-1,y-1,1);
}
memset(trace,0,sizeof(trace));
dfs1(0);
memset(trace,0,sizeof(trace));
dfs2(0,-1);
for(i=0;i<M;i++){
scanf("%d%d",&x,&y);
printf("%lld\n",max(h[x-1],u[x-1])+(y-1)*(long long)l[0]);
}
return 0;
}
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;
}
void dfs1(int x){
lnode *p;
trace[x]=1;
h[x]=sh[x]=l[x]=0;
for(p=table[x];p;p=p->next)
if(!trace[p->x]){
dfs1(p->x);
if(h[p->x]+p->w>=h[x]){
sh[x]=h[x];
h[x]=h[p->x]+p->w;
}
else if(h[p->x]+p->w>sh[x])
sh[x]=h[p->x]+p->w;
if(l[p->x]>l[x])
l[x]=l[p->x];
}
if(h[x]+sh[x]>l[x])
l[x]=h[x]+sh[x];
return;
}
void dfs2(int x,int y){
lnode *p;
trace[x]=1;
if(y==-1)
u[x]=0;
else
if(h[y]==h[x]+1)
u[x]=max(u[y]+1,sh[y]+1);
else
u[x]=max(u[y]+1,h[y]+1);
for(p=table[x];p;p=p->next)
if(!trace[p->x])
dfs2(p->x,x);
return;
}
int max(int x,int y){
return (x>y)?x:y;
}
```

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