Algorithm
Problem Name: Data Structures -
In this HackerRank in Data Structures -
Simon received the board game Ticket to Ride as a birthday present. After playing it with his friends, he decides to come up with a strategy for the game.
There are n cities on the map and n - 1 road plans. Each road plan consists of the following:
- Two cities which can be directly connected by a road.
- The length of the proposed road.
The entire road plan is designed in such a way that if one builds all the roads, it will be possible to travel between any pair of cities.
A ticket enables you to travel between two different cities. There are m tickets, and each ticket has a cost associated with it. A ticket is considered to be useful if there is a path between those cities. Simon wants to choose two cities, u and v and build a minimal number of roads so that they form a simple path between them. Let sl be the sum of costs of all useful tickets and sr be the sum of lengths of all the roads Simon builds. The profit for pair (u,v) is defined as sl - sr . Note that u and v are not necessarily unique and may be the same cities.
Given n road plans and m ticket prices, help Simon by printing the value of his maximum possible profit on a new line.
Input Format
The first line contains single positive integer, n enoting the number of cities.
Each of the n - 1 subsequent lines contains three space-separated integers describing the respective values of u,v and l for a road plan, where 1 <= u,v <= n and u not= v. Here, u and v are two cities that the road plan proposes to connect and l is the length of the proposed road.
The next line contains a single positive integer, m , denoting the number of tickets.
Each of the m subsequent lines contains three space-separated integers describing the respective values of u,v and c for a ticket from city u to city v (where c is the cost of the ticket).
Constraints
- 1 <= n <= 2 * 10**5
- 1 <= m <= 10**5
- 1 <= l,c <= 10**9
Output Format
Print a single integer denoting the the maximum profit Simon can make.
Time Limits
- 6 seconds for Java and C#.
- Please refer to our Environment page to see time limits for other languages.
Sample Input
7
1 2 1
1 3 1
1 4 4
4 5 1
4 6 1
4 7 1
5
5 7 3
3 6 2
3 4 10
2 7 15
1 6 7
Sample Output
13
Code Examples
#1 Code Example with C++ Programming
Code -
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::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::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 #2 Code Example with Java Programming
Code -
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[] down;
static List < Pair>[] up;
static List[] 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() {
Deque < NodeGo> deque = new LinkedList<>();
deque.add(new NodeGo(0, 0, null));
while (!deque.isEmpty()) {
NodeGo node = deque.peekLast();
if (node.start) {
if (node.p != null) {
add(node.p.first, 2 * node.p.second);
upd[1] -= node.p.second;
}
for (Pair p : other[node.u]) {
add(p.first, p.second);
}
for (Pair p : down[node.u]) {
add(p.first, -p.second);
upd[1] += p.second;
}
for (Pair p : up[node.u]) {
add(p.first, -p.second);
}
best = Math.max(best, get());
for (Pair p : g[node.u]) {
if (p.first == node.prev) {
continue;
}
deque.add(new NodeGo(p.first, node.u, p));
}
node.start = false;
} else {
for (Pair p : other[node.u]) {
add(p.first, -p.second);
}
for (Pair p : down[node.u]) {
add(p.first, p.second);
upd[1] -= p.second;
}
for (Pair p : up[node.u]) {
add(p.first, p.second);
}
if (node.p != null) {
add(node.p.first, -2 * node.p.second);
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() {
Deque < NodeDfs> deque = new LinkedList<>();
deque.add(new NodeDfs(0, 0, 0));
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 {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
StringTokenizer stk = new StringTokenizer(br.readLine());
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++) {
stk = new StringTokenizer(br.readLine());
int u = Integer.parseInt(stk.nextToken()) - 1;
int v = Integer.parseInt(stk.nextToken()) - 1;
int l = Integer.parseInt(stk.nextToken());
g[u].add(new Pair(v, l));
g[v].add(new Pair(u, l));
}
stk = new StringTokenizer(br.readLine());
int m = Integer.parseInt(stk.nextToken());
Pair[] tickets = new Pair[m];
int[] ticket_cost = new int[m];
for (int i = 0; i < m; i++) {
stk = new StringTokenizer(br.readLine());
int u = Integer.parseInt(stk.nextToken()) - 1;
int v = Integer.parseInt(stk.nextToken()) - 1;
int c = Integer.parseInt(stk.nextToken());
endings[u].add(i);
endings[v].add(i);
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];
add(v, c);
up[u].add(new Pair(v, c));
down[v].add(new Pair(u, c));
} else {
other[u].add(new Pair(v, c));
other[v].add(new Pair(u, c));
}
}
go();
bw.write(String.valueOf(best));
bw.newLine();
bw.close();
br.close();
}
}