# HackerRank Heavy Light White Falcon problem solution

In this HackerRank Heavy Light White Falcon problem, You are given a tree with N nodes and each node's value is initially 0. The problem asks you to operate the following two types of queries:

1. "1 u x" assign x to the value of the node u.
2. "2 u v" prints the maximum value of the nodes on the unique path between u and v.

## Problem solution in Python programming.

#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'solve' function below.
#
# The function is expected to return an INTEGER_ARRAY.
# The function accepts following parameters:
#  1. 2D_INTEGER_ARRAY tree
#  2. 2D_INTEGER_ARRAY queries
#
from collections import OrderedDict

def segtree_init(ary):
ary = list(ary)
seg = [ary]
while len(ary) > 1:
if len(ary) & 1: ary.append(0)
ary = [max(ary[i],ary[i+1]) for i in range(0,len(ary),2)]
seg.append(ary)
return seg

def segtree_set(seg, i, x):
ary = seg[0]
ary[i] = x
for j in range(1, len(seg)):
x = max(ary[i], ary[i^1])
ary = seg[j]
i >>= 1
ary[i] = x
def segtree_max(seg, lo, hi):
m = 0
j = 0
while lo < hi:
ary = seg[j]
if lo & 1:
x = ary[lo]
if x > m: m = x
lo += 1
if hi & 1:
hi -= 1
x = ary[hi]
if x > m: m = x
lo >>= 1
hi >>= 1
j += 1
return m

class heavy_light_node:
def __init__(self, segtree):
self.parent = None
self.pos = -1
self.segtree = segtree

def build_tree(i, edges, location):
children = []
members = [i]
ed = edges[i]
while ed:
for j in range(1,len(ed)):
child = build_tree(ed[j], edges, location)
child.pos = len(members) - 1
children.append(child)
i = ed[0]
members.append(i)
ed = edges[i]
node = heavy_light_node(segtree_init(0 for j in members))
for child in children:
child.parent = node
for j in range(len(members)):
location[members[j]] = (node, j)
return node

edges = [[] for i in range(N)]
for i in range(N-1):
x, y = map(int, input().split())
edges[x].append(y)
edges[y].append(x)
size = [0] * N
active = [0]
while active:
i = active[-1]
if size[i] == 0:
size[i] = 1
for j in edges[i]:
edges[j].remove(i)
active.append(j)
else:
active.pop()
edges[i].sort(key=lambda j: -size[j])
size[i] = 1 + sum(size[j] for j in edges[i])
location = [None] * N
build_tree(0, edges, location)
return location

def root_path(i, location):
loc = location[i]
path = [ loc ]
loc = loc[0]
while loc.parent != None:
path.append((loc.parent, loc.pos))
loc = loc.parent
path.reverse()
return path

def max_weight(x, y):
px = root_path(x, location)
py = root_path(y, location)
m = 1
stop = min(len(px), len(py))
while m < stop and px[m][0] == py[m][0]: m += 1
loc, a = px[m-1]
b = py[m-1][1]
if a > b: a, b = b, a
w = segtree_max(loc.segtree, a, b+1)
for j in range(m, len(px)):
loc, i = px[j]
x = segtree_max(loc.segtree, 0, i+1)
if x > w: w = x
for j in range(m, len(py)):
loc, i = py[j]
x = segtree_max(loc.segtree, 0, i+1)
if x > w: w = x
return w

N, Q = map(int, input().split())

for i in range(Q):
t, x, y = map(int, input().split())
if t == 1:
loc, i = location[x]
segtree_set(loc.segtree, i, y)
elif t == 2:
print(max_weight(x, y))

## Problem solution in Java Programming.

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {

/*
* Complete the 'solve' function below.
*
* The function is expected to return an INTEGER_ARRAY.
* The function accepts following parameters:
*  1. 2D_INTEGER_ARRAY tree
*  2. 2D_INTEGER_ARRAY queries
*/

public static List<Integer> solve(List<List<Integer>> edges, List<List<Integer>> queries) {

List<List<Integer>> nodes = new ArrayList<>();
for (int i = 0; i <= edges.size(); i++) {
}
for (int i = 0; i < edges.size(); i++) {
List<Integer> edge = edges.get(i);
int n1 = edge.get(0), n2 = edge.get(1);
}

// process root
List<List<Integer>> children = new ArrayList<>();
boolean[] visited = new boolean[nodes.size()];
for (int i = 0; i < nodes.size(); i++) {
}
stack.push(0);
while (!stack.isEmpty()) {
Integer current = stack.pop();
visited[current] = true;
for (Integer connection : nodes.get(current)) {
if (!visited[connection]) {
stack.push(connection);
}
}
}

HeavyLightDecompositionTree tree = new HeavyLightDecompositionTree(children);
for (List<Integer> query : queries) {
int operation = query.get(0), arg1 = query.get(1), arg2 = query.get(2);
if (operation == 1) { // update value
tree.update(arg1, arg2);
} else if (operation == 2) { // print max value
int maximum = tree.max(arg1, arg2);
}
}
return result;
}
}

class HeavyLightDecompositionTree {

private int[] parent, depth, heavy, head;
private Integer[] dfsPositions, dfsValues;
private SegmentTreeMax<Integer> segmentedPos;
private int[] values;

}

public HeavyLightDecompositionTree(List<List<Integer>> adj, int[] values) {
parent = new int[n];
Arrays.fill(parent, -1);
depth = new int[n];
heavy = new int[n];
Arrays.fill(heavy, -1);

dfsPositions = new Integer[n];
dfsValues = new Integer[n];
this.values = values;

segmentedPos = new SegmentTreeMax(dfsValues);
}

stack.push(0);
while (!stack.isEmpty()) {
int nodeId = stack.pop();
if (!visited[nodeId]) {
visited[nodeId] = true;
depth[nodeId] = parent[nodeId] != -1 ? depth[parent[nodeId]] + 1 : 1;

ListIterator<Integer> connectionsIterator = connections.listIterator(connections.size());
while (connectionsIterator.hasPrevious()) {
Integer connection = connectionsIterator.previous();
stack.push(nodeId);
stack.push(connection);
if (connection != parent[nodeId] && parent[connection] == -1) parent[connection] = nodeId;
}
}
if (connections.size() == 0) weight[nodeId] = 1;
else {
int childrenWeight = 1, maxChildSize = 0;
for (Integer connection : connections) {
int childSize = weight[connection];
if (connection != parent[nodeId]) childrenWeight += childSize;
if (childSize > maxChildSize) {
maxChildSize = childSize;
heavy[nodeId] = connection;
}
}
weight[nodeId] = childrenWeight;
}
}
}

int dfsPosition = 0;
stack.push(new int[]{0,0});
while (!stack.isEmpty()) {
int[] e = stack.pop();
int v = e[0], h = e[1];
dfsPositions[v] = dfsPosition;
dfsValues[dfsPosition] = 0;
dfsPosition++;
if (heavy[v] != -1) {
stack.push(new int[]{heavy[v], h});
}
for (int c : adj.get(v)) {
if (c != parent[v] && c != heavy[v]) {
}
}
}
}

public int max(int a, int b) {
int res = 0;
// swap(a, b);
int aux = a;
a = b;
b = aux;
}
res = Math.max(res, cur_heavy_path_max);
}
if (depth[a] > depth[b]) {
// swap(a, b);
int aux = a;
a = b;
b = aux;
}
int last_heavy_path_max = segmentedPos.max(dfsPositions[a], dfsPositions[b]);
res = Math.max(res, last_heavy_path_max);
return res;
}

public void update(int index, int value) {
//values[index] = value;
int dfsPosition = dfsPositions[index];
dfsValues[dfsPosition] = value;
segmentedPos.update(dfsPosition, value);
}
}

class SegmentTreeMax<T extends  Comparable> {

private T[] values;
private ArrayList<T> tree;

public SegmentTreeMax(T[] values) {
this.values = values;
this.tree = new ArrayList<T>(this.values.length * 4);
for (int i = 0; i < this.values.length * 4; i++) {
}
build(1, 0, values.length - 1);
}

private void build(int v, int tl, int tr) {
if (tl == tr) {
tree.set(v, values[tl]);
} else {
int tm = (tl + tr) / 2;
build(v * 2, tl, tm);
build(v * 2 + 1, tm + 1, tr);
T left = tree.get(v * 2),
right = tree.get(v * 2 + 1);
tree.set(v, left.compareTo(right) > 0 ? left : right);
}
}

public T max(int l, int r) {
return max(1, 0, values.length - 1, l, r);
}

public void update(int pos, T value) {
update(1, 0, values.length - 1, pos, value);
}

private void update(int v, int tl, int tr, int pos, T value) {
if (tl == tr) {
tree.set(v, value);
} else {
int tm = (tl + tr) / 2;
if (pos <= tm) {
update(v * 2, tl, tm, pos, value);
}
else {
update(v * 2 + 1, tm + 1, tr, pos, value);
}
T max1 = tree.get(v * 2),
max2 = tree.get(v * 2 + 1);
if (max1 == null && max2 == null) throw new NullPointerException("Cannot perform update with 2 nulls");
else if (max1 == null) tree.set(v, max2);
else if (max2 == null) tree.set(v, max1);
else tree.set(v, max1.compareTo(max2) > 0 ? max1 : max2);
}
}

private T max(int v, int tl, int tr, int l, int r) {
if (l > r)
return null; // return value that will not affect the reduction
if (l == tl && r == tr) {
return tree.get(v);
}
int tm = (tl + tr) / 2;
T max1 = max(v*2, tl, tm, l, Math.min(r, tm)),
max2 = max(v*2+1, tm+1, tr, Math.max(l, tm+1), r);
if (max1 == null && max2 == null) throw new NullPointerException("Cannot get a maximum value from 2 nulls");
else if (max1 == null) return max2;
else if (max2 == null) return max1;
else return max1.compareTo(max2) > 0 ? max1 : max2;
}

}

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

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

int q = Integer.parseInt(firstMultipleInput[1]);

List<List<Integer>> tree = new ArrayList<>();

IntStream.range(0, n - 1).forEach(i -> {
try {
.map(Integer::parseInt)
.collect(toList())
);
} catch (IOException ex) {
throw new RuntimeException(ex);
}
});

List<List<Integer>> queries = new ArrayList<>();

IntStream.range(0, q).forEach(i -> {
try {
.map(Integer::parseInt)
.collect(toList())
);
} catch (IOException ex) {
throw new RuntimeException(ex);
}
});

List<Integer> result = Result.solve(tree, queries);

bufferedWriter.write(
result.stream()
.map(Object::toString)
.collect(joining("\n"))
+ "\n"
);

bufferedWriter.close();
}
}

## Problem solution in C++ programming.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 50010;

class node {

public :
int l, r, mx;
node *left, *right;

void update(int idx, int val) {
if(l >= r) {
mx = val;
return;
}
int mid = (l + r) / 2;
(idx <= mid ? left : right)->update(idx, val);
mx = max(left->mx, right->mx);
}

int query(int a, int b) {
if(b < l or r < a) return 0;
if(a <= l and r <= b) return mx;
return max(left->query(a, b), right->query(a, b));
}

node(int _l, int _r) :
l(_l), r(_r), mx(0), left(NULL), right(NULL) {}
};

node* init(int l, int r) {
node *p = new node(l, r);
if(l < r) {
int mid = (l + r) / 2;
p->left = init(l, mid);
p->right = init(mid+1, r);
}
return p;
}

int n, q;

vector<int> Path[N];
int sz[N], H[N], P[N], G[N], pos[N];

void dfs_init(int u, int p, int h) {
P[u] = p;
H[u] = h;
sz[u] = 1;
if(v == p) {
continue;
}
dfs_init(v, u, h+1);
sz[u] += sz[v];
}
}
void dfs_HLD(int u) {
Path[u].push_back(u);
for(int i = 0;i < Path[u].size();i++) {
int v = Path[u][i];
G[v] = u;
pos[v] = i;
if(vv == P[v]) continue;
if(2*sz[vv] >= sz[v]) {
Path[u].push_back(vv);
}else {
dfs_HLD(vv);
}
}
}
head[u] = init(0, Path[u].size() - 1);
}
int query(int u, int v) {
int ans = 0;
while(G[u] != G[v]) {
if(H[G[u]] < H[G[v]]) {
swap(u, v);
}
u = P[G[u]];
}
if(pos[u] > pos[v]) {
swap(u, v);
}
return ans;
}
int main() {

ios::sync_with_stdio(false);
cin >> n >> q;
for(int i = 0;i < n-1;i++) {
int u, v;
cin >> u >> v;
}

dfs_init(0, 0, 0);
dfs_HLD(0);

for(int i = 0;i < q;i++) {
int type;
cin >> type;
if(type == 1) {
int u, x;
cin >> u >> x;
}else {
int u, v;
cin >> u >> v;
cout << query(u, v) << "\n";
}
}

return 0;
}

## Problem solution in C programming.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <stdint.h>
#include <assert.h>
#include <inttypes.h>

struct node1 *with;

typedef struct node1 {
int id;
int mark;
int num_connections;
} node1;

typedef struct segment {
struct segment *parent, *left, *right;
int height; //sideways and grows towards the root
int low_depth, high_depth; //low is numerically *greater*, low==high when leaf
int max_val;
} segment;

typedef struct node {
struct node *parent;
int sub_size; //includes self

int num_children;
struct node **children;

segment seg; //contains val and depth
} node;

node **out_storage = NULL;
node ***child_storage = NULL;
node **mapping = NULL;
node * directify(node1 *at, node *out_parent, int depth) {
//assert(!at->mark);
at->mark = 1;

node *out = *out_storage;
(*out_storage)++;

out->seg.max_val = 0;
out->seg.low_depth = depth;
out->seg.high_depth = depth;
out->seg.height = 0;
out->seg.left = out->seg.right = out->seg.parent = NULL;

out->parent = out_parent;
out->num_children = at->num_connections - 1;
out->children = (out->num_children == 0) ? NULL : *child_storage;
out->sub_size = 1;
(*child_storage) += out->num_children;

mapping[at->id] = out;

int ci = 0;
for (link *l = at->connections; l; l = l->next) {
node1 *to = l->with;
if (!to->mark) {
node *child = directify(to, out, depth + 1);
out->children[ci++] = child;
out->sub_size += child->sub_size;
}
}
assert(ci == out->num_children);

return out;
}

typedef struct segment_block {
struct segment_block *prev;
int use;
segment segs[1024];
} segment_block;

int max(int a, int b) {
return (a > b) ? a : b;
}

segment_block *front_block = NULL;
segment * new_segment(segment *left_child, segment *right_child) {
if (!front_block || front_block->use == 1024) {
segment_block *last = front_block;
front_block = (segment_block*)calloc(1, sizeof(segment_block));
front_block->prev = last;
front_block->use = 0;
}
segment *seg = &front_block->segs[front_block->use++];
//assert(left_child && right_child);
//assert(left_child->low_depth >= left_child->high_depth);
//assert(right_child->low_depth >= right_child->high_depth);
//assert(left_child->high_depth > right_child->low_depth);

seg->low_depth = left_child->low_depth;
seg->high_depth = right_child->high_depth;
seg->height = max(left_child->height, right_child->height) + 1;
seg->left = left_child;
seg->right = right_child;
seg->max_val = max(left_child->max_val, right_child->max_val);
seg->parent = NULL;
left_child->parent = seg;
right_child->parent = seg;

return seg;
}

void build_chain_tree(node *final, node *chain_head, int chain_length) {
static segment **stack = NULL;
static int stack_length = 0;

if (stack_length < chain_length) {
stack_length = chain_length;
stack = (segment**)realloc(stack, stack_length * sizeof(segment*));
}

node *at = final;
int stack_size = 0;
stack[stack_size] = &at->seg;
stack_size++;
at = at->parent;

while (stack_size > 1) {
segment *r = stack[stack_size - 1];
segment *l = stack[stack_size - 2];
if (r->height == l->height) {
segment *p = new_segment(l, r);
stack[stack_size - 2] = p;
stack_size--;
}
else {
break;
}
}
}

//assert(stack_size >= 1);
while (stack_size > 1) {
segment *r = stack[stack_size - 1];
segment *l = stack[stack_size - 2];
//assert(r->height <= l->height);
segment *p = new_segment(l, r);
stack[stack_size - 2] = p;
stack_size--;
}
}

void hld(node *at, node *chain_head, int chain_length, int *num_chains) {
(*num_chains)++;
}

node *most = NULL;
for (int ci = 0; ci < at->num_children; ci++) {
if (!most || most->sub_size < at->children[ci]->sub_size) {
most = at->children[ci];
}
}

for (int ci = 0; ci < at->num_children; ci++) {
node *ch = at->children[ci];
if (ch == most) {
//continue chain
hld(ch, chain_head, chain_length + 1, num_chains);
}
else {
//start new chain
hld(ch, NULL, 1, num_chains);
}

}

if (!most) {
//end of chain, build tree
}
}

node * lca(node *u, node *v) {
else
}
return (u->seg.low_depth < v->seg.low_depth) ? u : v;
}

int segment_range_query(segment *at, int low_depth, int high_depth) {
//assert(low_depth >= high_depth);
//assert(at->low_depth >= low_depth);
//assert(at->high_depth <= high_depth);

if (at->low_depth == low_depth && at->high_depth == high_depth) {
return at->max_val;
}
else {
if (high_depth >= at->left->high_depth) {
return segment_range_query(at->left, low_depth, high_depth);
}
else if (low_depth <= at->right->low_depth) {
return segment_range_query(at->right, low_depth, high_depth);
}
else {
return max(segment_range_query(at->left, low_depth, at->left->high_depth),
segment_range_query(at->right, at->right->low_depth, high_depth));
}
}
}

int path_max_inner(node *higher, node* lower) {
int64_t max_val = 0;
//assert(lower && higher);

segment *seg = &lower->seg;
while (seg->parent) seg = seg->parent;
max_val = max(max_val, segment_range_query(seg, lower->seg.low_depth, seg->high_depth));
}
//assert(lower && higher);

segment *seg = &lower->seg;
while (seg->parent) seg = seg->parent;
max_val = max(max_val, segment_range_query(seg, lower->seg.low_depth, higher->seg.high_depth));
return max_val;
}

int path_max(node *u, node *v) {
if (u == v) {
return u->seg.max_val;
}
else {
node *pivot = lca(u, v);
//assert(pivot);
//assert(pivot->seg.low_depth <= u->seg.low_depth);
//assert(pivot->seg.low_depth <= v->seg.low_depth);

int ml = path_max_inner(pivot, u);
int mr = path_max_inner(pivot, v);
return max(ml, mr);
}
}

void segment_update(segment *at) {
while (at) {
at->max_val = max(at->left->max_val, at->right->max_val);
at = at->parent;
}
}

int main() {
int n, q;
scanf("%d %d", &n, &q);

node1 *initial = (node1*)calloc(n, sizeof(node1));

for (int i = 0; i < n; i++) {
initial[i].id = i;
}

for (int i = 0; i < n - 1; i++) {
int ai, bi;
scanf("%d %d", &ai, &bi);

node1* a = &initial[ai];
node1* b = &initial[bi];

la->next = a->connections;
lb->next = b->connections;

la->with = b;
lb->with = a;

a->num_connections++;
b->num_connections++;

a->connections = la;
b->connections = lb;
}

node **child_links = (node**)malloc((n - 1) * sizeof(node*));
node *processed = (node*)calloc(n, sizeof(node));
mapping = (node**)calloc(n, sizeof(node*));

//convert to tree, node 0 as root
node *procp = processed; out_storage = &procp;
node **clp = child_links; child_storage = &clp;

initial[0].num_connections++; //root only has connections to children
directify(&initial[0], NULL, 0);

assert(procp == processed + n);
assert(clp == child_links + (n - 1));

free(initial); initial = NULL;

//heavy-light decoposition
int num_chains = 0;
hld(&processed[0], NULL, 1, &num_chains);

//queries
for (int i = 0; i < q; i++) {
int t, ui, vi;
scanf("%d %d %d", &t, &ui, &vi);

if (t == 1) {
node *u = mapping[ui];
u->seg.max_val = vi;
segment_update(u->seg.parent);
}

else {
node *u = mapping[ui];
node *v = mapping[vi];
int val = path_max(u, v);
printf("%d\n", val);
}
}

return 0;
}