# HackerRank Ticket to Ride problem solution

In this HackerRank Ticket to Ride problem we have given n road plans and m ticket prices, help Simon by printing the value of his maximum possible profit on a new line.

## Problem solution in Java Programming.

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

public class Solution {

static final int BASE = 1 << 19;
static long[] t = new long[BASE * 2];
static long[] upd = new long[BASE * 2];

static long get() {
return t[1] + upd[1];
}

static int l, r, delta;

static void put(int v, int cl, int cr) {
if (r <= cl || cr <= l) {
return;
}
if (l <= cl && cr <= r) {
upd[v] += delta;
return;
}
int cc = (cl + cr) >> 1;
put(v << 1, cl, cc);
put((v << 1) + 1, cc, cr);
t[v] = Math.max(t[v << 1] + upd[v << 1], t[(v << 1) + 1] + upd[(v << 1) + 1]);
}

static int[] in;
static int[] out;

static void add(int v, int deltat) {
l = in[v];
r = out[v];
delta = deltat;
put(1, 0, BASE);
}

static boolean isPrev(int u, int v) {
return in[u] <= in[v] && out[v] <= out[u];
}

static class Pair {
int first;
int second;

public Pair(int first, int second) {
this.first = first;
this.second = second;
}
}

static List<Pair>[] other;
static List<Pair>[] down;
static List<Pair>[] up;
static List<Pair>[] g;

static long best = 0;

static class NodeGo {
int u;
int prev;
Pair p;
boolean start = true;

public NodeGo(int u, int prev, Pair p) {
this.u = u;
this.prev = prev;
this.p = p;
}
}

static void go() {

while (!deque.isEmpty()) {
NodeGo node = deque.peekLast();

if (node.start) {
if (node.p != null) {
upd[1] -= node.p.second;
}

for (Pair p : other[node.u]) {
}
for (Pair p : down[node.u]) {
upd[1] += p.second;
}
for (Pair p : up[node.u]) {
}
best = Math.max(best, get());

for (Pair p : g[node.u]) {
if (p.first == node.prev) {
continue;
}
}

node.start = false;
} else {
for (Pair p : other[node.u]) {
}
for (Pair p : down[node.u]) {
upd[1] -= p.second;
}
for (Pair p : up[node.u]) {
}

if (node.p != null) {
upd[1] += node.p.second;
}

deque.removeLast();
}
}
}

static int sc = 0;
static int[] st;
static int[] visits;
static int[] needh;
static int[] step;
static int timer = 0;
static List<Integer>[] endings;

static class NodeDfs {
int u;
int p;
long depth;
boolean start = true;

public NodeDfs(int u, int p, long depth) {
this.u = u;
this.p = p;
this.depth = depth;
}
}

static void dfs() {

while (!deque.isEmpty()) {
NodeDfs node = deque.peekLast();

if (node.start) {
st[sc++] = node.u;
for (int id : endings[node.u]) {
visits[id]++;
if (visits[id] == 1) {
needh[id] = sc;
} else if (visits[id] == 2) {
step[id] = st[needh[id]];
}
}
in[node.u] = timer++;
t[in[node.u] + BASE] = -node.depth;

for (Pair p : g[node.u]) {
if (p.first != node.p) {
deque.add(new NodeDfs(p.first, node.u, node.depth + p.second));
}
}

node.start = false;
} else {
for (int id : endings[node.u]) {
visits[id]--;
}
out[node.u] = timer;
--sc;

deque.removeLast();
}
}
}

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

int n = Integer.parseInt(stk.nextToken());

other = new List[n];
down = new List[n];
up = new List[n];
g = new List[n];
endings = new List[n];

for (int i = 0; i < g.length; i++) {
g[i] = new ArrayList<>();
endings[i] = new ArrayList<>();
other[i] = new ArrayList<>();
up[i] = new ArrayList<>();
down[i] = new ArrayList<>();
}

for (int i = 0; i < n - 1; i++) {
int u = Integer.parseInt(stk.nextToken()) - 1;
int v = Integer.parseInt(stk.nextToken()) - 1;
int l = Integer.parseInt(stk.nextToken());
}

int m = Integer.parseInt(stk.nextToken());
Pair[] tickets = new Pair[m];
int[] ticket_cost = new int[m];

for (int i = 0; i < m; i++) {
int u = Integer.parseInt(stk.nextToken()) - 1;
int v = Integer.parseInt(stk.nextToken()) - 1;
int c = Integer.parseInt(stk.nextToken());
tickets[i] = new Pair(u, v);
ticket_cost[i] = c;
}

step = new int[m];
Arrays.fill(step, -1);
in = new int[n];
out = new int[n];
st = new int[n];
visits = new int[m];
needh = new int[m];

dfs();
for (int i = BASE - 1; i > 0; --i) {
t[i] = Math.max(t[i * 2], t[i * 2 + 1]);
}

for (int i = 0; i < m; i++) {
int u = tickets[i].first;
int v = tickets[i].second;
int c = ticket_cost[i];
if (isPrev(v, u)) {
int temp = u;
u = v;
v = temp;
}
if (isPrev(u, v)) {
u = step[i];
} else {
}
}
go();

bw.write(String.valueOf(best));
bw.newLine();

bw.close();
br.close();
}
}```

## Problem solution in C++ programming.

```#include <algorithm>
#include <climits>
#include <iostream>
#include <type_traits>
#include <utility>
#include <vector>
using namespace std;

#define FOR(i, a, b) for (remove_cv<remove_reference<decltype(b)>::type>::type i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define ROF(i, a, b) for (remove_cv<remove_reference<decltype(b)>::type>::type i = (b); --i >= (a); )

const long N = 200000, NN = 1 << 63-__builtin_clzl(N-1)+1, M = 100000;
long st[N], dep[N], pre[N], post[N], tick, mx[2*NN], dlt[2*NN], opt;
vector<pair<long, long>> adj[N], ticket[N], other[N], down[N], up[N];

void mconcat(long i)
{
mx[i] = max(mx[2*i]+dlt[2*i], mx[2*i+1]+dlt[2*i+1]);
}

{
bool lf = false, rf = false;
long l = NN+pre[u], r = NN+post[u];
while (l < r) {
if (l & 1) lf = true, dlt[l++] += x;
l >>= 1;
if (lf) mconcat(l-1);
if (r & 1) rf = true, dlt[--r] += x;
r >>= 1;
if (rf) mconcat(r);
}
for (l--; l >>= 1, r >>= 1; ) {
if (lf || l == r) mconcat(l);
if (rf && l != r) mconcat(r);
}
}

void dfs(long d, long sum, long u)
{
dep[u] = d;
st[d] = u;
mx[NN+tick] = - sum;
pre[u] = tick++;
post[u] = LONG_MAX;
long x = 0;
for (auto e: ticket[u])
if (post[e.first]) {
long v = e.first, cost = e.second;
if (post[v] == LONG_MAX) {
long w = st[dep[v]+1];
down[w].emplace_back(u, cost);
up[u].emplace_back(w, cost);
x += cost;
} else {
other[u].emplace_back(v, cost);
other[v].emplace_back(u, cost);
}
}
if (! post[e.first])
dfs(d+1, sum+e.second, e.first);
post[u] = tick;
}

void calc(long u, long p)
{
for (auto e: other[u])
for (auto e: down[u])
for (auto e: up[u]) {
dlt[1] += e.second;
}
opt = max(opt, mx[1]+dlt[1]);
if (e.first != p) {
dlt[1] -= e.second;
calc(e.first, u);
dlt[1] += e.second;
}
for (auto e: other[u])
for (auto e: down[u])
for (auto e: up[u]) {
dlt[1] -= e.second;
}
}

int main()
{
ios_base::sync_with_stdio(0);
long n, m, u, v, w;
cin >> n;
REP(i, n-1) {
cin >> u >> v >> w;
u--, v--;
}
cin >> m;
REP(i, m) {
cin >> u >> v >> w;
u--, v--;
ticket[u].emplace_back(v, w);
ticket[v].emplace_back(u, w);
}
dfs(0, 0, 0);
ROF(i, 1, NN)
mconcat(i);
calc(0, -1);
cout << opt << endl;
}```