# HackerRank Lazy White Falcon problem solution

In this HackerRank Lazy White Falcon problem, we have given a tree with N nodes where each node's value is initially 0 and we need to execute Q queries.

## Problem solution in Python programming.

```#!/bin/python3

import os
import sys
import math

sys.setrecursionlimit(10**6)

def roundup(x):
k = 1 << (x.bit_length()-1)
if k < x:
return 2*k
return k

def update(t,i,x,op):
t[i] = x
while i > 1:
i >>= 1
t[i] = op(t[2*i],t[2*i+1])

def rangequery(t,a,b,op,init): # assumes op is of abelian monoid
s = init
while a < b:
if a & 1:
s = op(s,t[a])
a += 1
if b & 1:
s = op(s,t[b-1])
b -= 1
a >>= 1
b >>= 1
return s

def rangeify(l,op,init):
off = roundup(len(l))
r = [init for _ in range(off)] + l + [init for _ in range(off-len(l))]
for i in range(off-1,0,-1):
r[i] = op(r[2*i],r[2*i+1])
return (r,off)

# Complete the solve function below.
def solve(tree, queries):
N = len(tree) + 1
neighbors = [[] for _ in range(N)]

for edge in tree:
neighbors[edge[0]].append(edge[1])
neighbors[edge[1]].append(edge[0])

heights = []
eulerian = []
outs = []
epos = [[-1,-1] for _ in range(N)]
heightpos = [-1 for _ in range(N)]
def dfs(node, parent, height):
eulerian.append(0)
epos[node][0] = len(eulerian)-1
heights.append((height,node))
heightpos[node] = len(heights) - 1
for n in neighbors[node]:
if n != parent:
dfs(n, node, height+1)
heights.append((height,node))
eulerian.append(0)
epos[node][1] = len(eulerian) - 1
dfs(0,-1,0)
htree, hoff = rangeify(heights,lambda x,y: min(x,y), (math.inf,math.inf))
eulerian, off = rangeify(eulerian, lambda x,y: x+y, 0)
epos = [[x[0]+off,x[1]+off] for x in epos]
heightpos = [x + hoff for x in heightpos]
def lca(u,v):
low, high = heightpos[u],heightpos[v]
low, high = min(low,high),max(low,high)
return rangequery(htree,
low,
high+1,
lambda x,y: min(x,y),
(math.inf,math.inf))
def pathsum(u,v):
a = lca(u,v)[1]
ou = rangequery(eulerian,epos[0][0],epos[u][0]+1,lambda x,y: x+y,0)
ov = rangequery(eulerian,epos[0][0],epos[v][0]+1,lambda x,y: x+y,0)
oa = rangequery(eulerian,epos[0][0],epos[a][0]+1,lambda x,y: x+y,0)
return ou + ov - 2*oa + eulerian[epos[a][0]]
for query in queries:
if query[0] == 1:
u = query[1]
x = query[2]
update(eulerian,epos[u][0],x,lambda x,y: x+y)
update(eulerian,epos[u][1],-x,lambda x,y: x+y)
else:
u = query[1]
v = query[2]
outs.append(pathsum(u,v))

print(htree)
print(heightpos)
print(epos)
print(eulerian, off)
return outs

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

nq = input().split()

n = int(nq[0])

q = int(nq[1])

tree = []

for _ in range(n-1):
tree.append(list(map(int, input().rstrip().split())))

queries = []

for _ in range(q):
queries.append(list(map(int, input().rstrip().split())))

result = solve(tree, queries)

fptr.write('\n'.join(map(str, result)))
fptr.write('\n')

fptr.close()```

## Problem solution in Java Programming.

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

class Node {
int id;
Node parent;
List<Node> children;
List<Node> connections;
int value;

public Node(int id) {
this.id = id;
}

}

child.parent = this;
}

public void updateValue(int nodeId, int value) {
Node toUpdateNode = nodes[nodeId];
int increment = value - toUpdateNode.value;
toUpdateNode.value = value;
int firstEuler = eulerFirsts[toUpdateNode.id],
lastEuler = eulerLasts[toUpdateNode.id];
int startIndex = Math.min(firstEuler, lastEuler),
endIndex = Math.max(firstEuler, lastEuler);
this.rootAggregates.update(startIndex, endIndex, increment);
}

public int rootAggregation(int nodeId) {
Node toUpdateNode = nodes[nodeId];
int firstEuler = eulerFirsts[toUpdateNode.id];
return this.rootAggregates.get(firstEuler);
}

public boolean isParent(Node another) {
return this.parent != null && this.parent.id == another.id;
}

public int LCAIndex(int n1, int n2) {
int n1EulerAppearance = eulerFirsts[n1],
n2EulerAppearance = eulerFirsts[n2];
int startIndex = Math.min(n1EulerAppearance, n2EulerAppearance),
endIndex = Math.max(n1EulerAppearance, n2EulerAppearance) + 1;
EulerNode lcaNode = eulerNodes.min(startIndex, endIndex);
return lcaNode.vertex;
}

private int[] eulerFirsts;
private int[] eulerLasts;
private int[] eulerPath;
private Node[] nodes;
private SegmentTreeMin<EulerNode> eulerNodes;
public void processLCA(Node[] nodes) {
this.nodes = nodes;
boolean[] visited = new boolean[nodes.length];
this.eulerFirsts = new int[nodes.length];
Arrays.fill(this.eulerFirsts, -1);
this.eulerLasts = new int[nodes.length];
Arrays.fill(this.eulerLasts, -1);
stack.push(this);
int depth = 1;
while(!stack.isEmpty()) {
Node current = stack.pop();
int eulerLength = eulerPath.size() - 1;
if (this.eulerFirsts[current.id] == -1) {
this.eulerFirsts[current.id] = eulerLength;
}
if (this.eulerLasts[current.id] == -1 || eulerLength > this.eulerLasts[current.id]) {
this.eulerLasts[current.id] = eulerLength;
}
if (!visited[current.id]) {
visited[current.id] = true;
for (Node child : current.children) {
stack.push(current);
stack.push(child);
}
}
Node next = stack.peekFirst();
if (next != null && next.isParent(current)) depth++;
else depth--;
}
int[] vertices = eulerPath.stream().mapToInt(n -> n.id).toArray();
int[] heights = eulerHeights.stream().mapToInt(Integer::intValue).toArray();
EulerNode[] eulerNodes = new EulerNode[eulerPath.size()];
for (int i = 0; i < heights.length; i++) {
eulerNodes[i] = new EulerNode(heights[i], vertices[i]);
}
this.eulerNodes = new SegmentTreeMin<>(eulerNodes);
this.eulerPath = vertices;
this.rootAggregates = new SegmentTreeSegmentedAddition( new int[this.eulerPath.length] );
}
public void processRoot() {
stack.push(this);
while (!stack.isEmpty()) {
Node current = stack.pop();
for (Node connection : current.connections) {
if (connection == current || connection == current.parent) continue;
stack.push(connection);
}
}
}
}

class EulerNode implements Comparable {
int height;
int vertex;

public EulerNode(int height, int vertex) {
this.height = height;
this.vertex = vertex;
}

@Override
public int compareTo(Object o) {
EulerNode other = (EulerNode)o;
return this.height - other.height;
}
}

private int[] values;
private int[] tree;

this.values = values;
this.tree = new int[values.length * 4];
build(1, 0, values.length - 1);
}

private void build(int v, int tl, int tr) {
if (tl == tr) {
tree[v] = values[tl];
} else {
int tm = (tl + tr) / 2;
build(v * 2, tl, tm);
build(v * 2 + 1, tm + 1, tr);
tree[v] = 0;
}
}

public void update(int l, int r, int add) {
this.update(1, 0, values.length - 1, l, r, add);
}

private void update(int v, int tl, int tr, int l, int r, int add) {
if (l > r)
return;
if (l == tl && r == tr) {
} else {
int tm = (tl + tr) / 2;
update(v * 2, tl, tm, l, Math.min(r, tm), add);
update(v * 2 + 1, tm + 1, tr, Math.max(l, tm + 1), r, add);
}
}

public int get(int pos) {
return this.get(1, 0, values.length - 1, pos);
}

private int get(int v, int tl, int tr, int pos) {
if (tl == tr)
return tree[v];
int tm = (tl + tr) / 2;
if (pos <= tm)
return tree[v] + get(v * 2, tl, tm, pos);
else
return tree[v] + get(v * 2 + 1, tm + 1, tr, pos);
}
}

class SegmentTreeMin<T extends  Comparable> {

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

public SegmentTreeMin(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 min(int l, int r) {
return min(1, 0, values.length - 1, l, r);
}

private T min(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 min1 = min(v*2, tl, tm, l, Math.min(r, tm)),
min2 = min(v*2+1, tm+1, tr, Math.max(l, tm+1), r);
if (min1 == null && min2 == null) throw new NullPointerException("Cannot retrieve minimum value from 2 nulls");
else if (min1 == null) return min2;
else if (min2 == null) return min1;
else return min1.compareTo(min2) < 0 ? min1 : min2;
}

}

public class Solution {

static int[] solve(int[][] edges, int[][] queries) {
Node[] nodes = new Node[edges.length + 1];
for (int i = 0; i < edges.length; i++) {
Node node1 = nodes[n1] != null ? nodes[n1] : new Node(n1),
node2 = nodes[n2] != null ? nodes[n2] : new Node(n2);
nodes[n1] = node1;
nodes[n2] = node2;
}

Node root = nodes[0];
root.processRoot();

root.processLCA(nodes);

for (int[] query : queries) {
int operation = query[0], arg1 = query[1], arg2 = query[2];
if (operation == 1) { // update value
root.updateValue(arg1, arg2);
} else if (operation == 2) { // print path aggregation
if (arg1 == arg2) {
}
else {
int lcaIndex = root.LCAIndex(arg1, arg2);
int lcaValue = root.rootAggregation(nodes[lcaIndex].id),
n1Aggregation = root.rootAggregation(nodes[arg1].id),
n2Aggregation = root.rootAggregation(nodes[arg2].id);
int rootAggregationOffset = 0;
if (lcaIndex != root.id) {
rootAggregationOffset += root.rootAggregation(nodes[lcaIndex].parent.id);
}
int aggregation = n1Aggregation + n2Aggregation - lcaValue - rootAggregationOffset;
}
}
}

return result.stream().mapToInt(Integer::intValue).toArray();
}

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[] nq = scanner.nextLine().split(" ");

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

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

int[][] tree = new int[n-1][2];

for (int treeRowItr = 0; treeRowItr < n-1; treeRowItr++) {
String[] treeRowItems = scanner.nextLine().split(" ");
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

for (int treeColumnItr = 0; treeColumnItr < 2; treeColumnItr++) {
int treeItem = Integer.parseInt(treeRowItems[treeColumnItr]);
tree[treeRowItr][treeColumnItr] = treeItem;
}
}

int[][] queries = new int[q][3];

for (int queriesRowItr = 0; queriesRowItr < q; queriesRowItr++) {
String[] queriesRowItems = scanner.nextLine().split(" ");
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

for (int queriesColumnItr = 0; queriesColumnItr < 3; queriesColumnItr++) {
int queriesItem = Integer.parseInt(queriesRowItems[queriesColumnItr]);
queries[queriesRowItr][queriesColumnItr] = queriesItem;
}
}

int[] result = solve(tree, queries);

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();
}
}```

## Problem solution in C++ programming.

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

using namespace std;

vector<string> split_string(string);

struct Node
{
int path;
int size;
int depth;
int parent;
};

struct Path
{
int root;
int depth;
int size;
vector<int> sums;

int sum(int ti, int tl, int tr, int l, int r)
{
if (l <= r)
{
if (l == tl && r == tr)
{
return sums[ti];
}
else
{
int tm = (tl + tr) / 2;
return sum(2 * ti, tl, tm, l, min(r, tm)) + sum(2 * ti + 1, tm + 1, tr, max(l, tm + 1), r);
}
}
return 0;
}

void assign(int value, int ti, int tl, int tr, int i)
{
if (i == tl && i == tr)
{
sums[ti] = value;
}
else
{
int tm = (tl + tr) / 2;
if (i <= tm)
{
assign(value, 2 * ti, tl, tm, i);
}
else
{
assign(value, 2 * ti + 1, tm + 1, tr, i);
}
sums[ti] = sums[2 * ti] + sums[2 * ti + 1];
}
}

void assign(int i, int v)
{
assign(v, 1, 0, size - 1, i);
}

int sum(int l, int r)
{
return sum(1, 0, size - 1, l, r);
}

Path(int root, int depth, int size) : root(root), depth(depth), size(size)
{
int temp = 1;
while (temp <= size)
{
temp <<= 1;
}
sums.resize(2 * temp, 0);
}
};

class Tree
{
vector<Path> paths;
vector<Node> nodes;

bool isHeavy(int node)
{
int parent = nodes[node].parent;
return (parent < 0) ? false : (2 * nodes[node].size >= nodes[parent].size);
}

public:
Tree(vector<vector<int>>& edges)
{
vector<vector<int>> tree(edges.size() + 1);
for (int i = 0; i < edges.size(); i++)
{
tree[edges[i][0]].push_back(edges[i][1]);
tree[edges[i][1]].push_back(edges[i][0]);
}

nodes.resize(edges.size() + 1);
init(0, -1, 0, tree);
createPaths(0, -1, tree);
}

void init(int curr, int parent, int depth, vector<vector<int>>& tree)
{
nodes[curr].size = 1;
nodes[curr].depth = depth;
nodes[curr].parent = parent;
for (int i = 0; i < tree[curr].size(); i++)
{
int next = tree[curr][i];
if (next != parent)
{
init(next, curr, depth + 1, tree);
nodes[curr].size += nodes[next].size;
}
}
}

void createPaths(int curr, int parent, vector<vector<int>>& tree)
{
bool hasHeavy = false;
for (int i = 0; i < tree[curr].size(); i++)
{
int next = tree[curr][i];
if (next != parent)
{
createPaths(next, curr, tree);
if (isHeavy(next))
{
hasHeavy = true;
}
}
}
if (!hasHeavy)
{
createPath(curr);
}
}

void createPath(int node)
{
int length = 1;
while (true)
{
nodes[node].path = paths.size();
if (!isHeavy(node))
{
break;
}
node = nodes[node].parent;
length += 1;
}
paths.push_back(Path(node, nodes[node].depth, length));
}

void assign(int node, int value)
{
int path = nodes[node].path;
paths[path].assign(nodes[node].depth - paths[path].depth, value);
}

int sum(int u, int v)
{
if (nodes[u].path == nodes[v].path)
{
int path = nodes[u].path;
int l = std::min(nodes[u].depth, nodes[v].depth);
int r = std::max(nodes[u].depth, nodes[v].depth);
return paths[path].sum(l - paths[path].depth, r - paths[path].depth);
}
int rootU = paths[nodes[u].path].root;
int rootV = paths[nodes[v].path].root;
if (nodes[rootU].depth < nodes[rootV].depth)
{
int path = nodes[v].path;
return paths[path].sum(0, nodes[v].depth - paths[path].depth) + sum(u, nodes[rootV].parent);
}
else
{
int path = nodes[u].path;
return paths[path].sum(0, nodes[u].depth - paths[path].depth) + sum(nodes[rootU].parent, v);
}
}
};

vector<int> solve(vector<vector<int>>& edges, vector<vector<int>>& queries)
{
Tree tree(edges);
vector<int> res;
for (int i = 0; i < queries.size(); i++)
{
if (queries[i][0] == 1)
{
tree.assign(queries[i][1], queries[i][2]);
}
else
{
res.push_back(tree.sum(queries[i][1], queries[i][2]));
}
}
return res;
}

int main()
{
ofstream fout(getenv("OUTPUT_PATH"));

string nq_temp;
getline(cin, nq_temp);

vector<string> nq = split_string(nq_temp);

int n = stoi(nq[0]);

int q = stoi(nq[1]);

vector<vector<int>> tree(n-1);
for (int tree_row_itr = 0; tree_row_itr < n-1; tree_row_itr++) {
tree[tree_row_itr].resize(2);

for (int tree_column_itr = 0; tree_column_itr < 2; tree_column_itr++) {
cin >> tree[tree_row_itr][tree_column_itr];
}

cin.ignore(numeric_limits<streamsize>::max(), '\n');
}

vector<vector<int>> queries(q);
for (int queries_row_itr = 0; queries_row_itr < q; queries_row_itr++) {
queries[queries_row_itr].resize(3);

for (int queries_column_itr = 0; queries_column_itr < 3; queries_column_itr++) {
cin >> queries[queries_row_itr][queries_column_itr];
}

cin.ignore(numeric_limits<streamsize>::max(), '\n');
}

vector<int> result = solve(tree, queries);

for (int result_itr = 0; result_itr < result.size(); result_itr++) {
fout << result[result_itr];

if (result_itr != result.size() - 1) {
fout << "\n";
}
}

fout << "\n";

fout.close();

return 0;
}

vector<string> split_string(string input_string) {
string::iterator new_end = unique(input_string.begin(), input_string.end(), [] (const char &x, const char &y) {
return x == y and x == ' ';
});

input_string.erase(new_end, input_string.end());

while (input_string[input_string.length() - 1] == ' ') {
input_string.pop_back();
}

vector<string> splits;
char delimiter = ' ';

size_t i = 0;
size_t pos = input_string.find(delimiter);

while (pos != string::npos) {
splits.push_back(input_string.substr(i, pos - i));

i = pos + 1;
pos = input_string.find(delimiter, i);
}

splits.push_back(input_string.substr(i, min(pos, input_string.length()) - i + 1));

return splits;
}```

## Problem solution in C programming.

```#include <stdio.h>
#include <stdlib.h>
typedef struct _lnode{
int x;
int w;
struct _lnode *next;
} lnode;
typedef struct _tree{
int sum;
} tree;
void insert_edge(int x,int y,int w);
void dfs0(int u);
void dfs1(int u,int c);
void preprocess();
int lca(int a,int b);
int sum(int v,int tl,
int tr,int l,int r,tree *t);
void update(int v,int tl,
int tr,int pos,int new_val,tree *t);
int min(int x,int y);
int max(int x,int y);
int solve(int x,int ancestor);
int N,cn,level[100000],DP[18][100000],
subtree_size[100000],special[100000],
node_chain[100000],node_idx[100000],
lnode *table[100000]={0};
tree *chain[100000];

int main(){
int Q,x,y,i;
scanf("%d%d",&N,&Q);
for(i=0;i<N-1;i++){
scanf("%d%d",&x,&y);
insert_edge(x,y,1);
}
preprocess();
while(Q--){
scanf("%d",&x);
switch(x){
case 1:
scanf("%d%d",&x,&y);
update(1,0,chain_len[node_chain[x]]
-1,node_idx[x],y,chain[node_chain[x]]);
break;
default:
scanf("%d%d",&x,&y);
i=lca(x,y);
printf("%d\n",
solve(x,i)+solve(y,i)-
sum(1,0,chain_len[node_chain[i]]
-1,node_idx[i],node_idx[i],chain[node_chain[i]]));
}
}
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 dfs0(int u){
lnode *x;
subtree_size[u]=1;
special[u]=-1;
for(x=table[u];x;x=x->next)
if(x->x!=DP[0][u]){
DP[0][x->x]=u;
level[x->x]=level[u]+1;
dfs0(x->x);
subtree_size[u]+=subtree_size[x->x];
if(special[u]==-1 ||
subtree_size[x->x]>subtree_size[special[u]])
special[u]=x->x;
}
return;
}
void dfs1(int u,int c){
lnode *x;
node_chain[u]=c;
node_idx[u]=chain_len[c]++;
for(x=table[u];x;x=x->next)
if(x->x!=DP[0][u])
if(x->x==special[u])
dfs1(x->x,c);
else{
dfs1(x->x,cn++);
}
return;
}
void preprocess(){
int i,j;
level[0]=0;
DP[0][0]=0;
dfs0(0);
for(i=1;i<18;i++)
for(j=0;j<N;j++)
DP[i][j] = DP[i-1][DP[i-1][j]];
cn=1;
dfs1(0,0);
for(i=0;i<cn;i++)
chain[i]=(tree*)malloc(
4*chain_len[i]*sizeof(tree));
for(i=0;i<N;i++)
update(1,0,chain_len[node_chain[i]]-1,
node_idx[i],0,chain[node_chain[i]]);
return;
}
int lca(int a,int b){
int i;
if(level[a]>level[b]){
i=a;
a=b;
b=i;
}
int d = level[b]-level[a];
for(i=0;i<18;i++)
if(d&(1<<i))
b=DP[i][b];
if(a==b)return a;
for(i=17;i>=0;i--)
if(DP[i][a]!=DP[i][b])
a=DP[i][a],b=DP[i][b];
return DP[0][a];
}
int sum(int v,int tl,int tr,int l,
int r,tree *t){
if(l>r)
return 0;
if(l==tl && r==tr)
return t[v].sum;
int tm=(tl+tr)/2;
return sum(v*2,tl,tm,l,min(r,tm),t)+
sum(v*2+1,tm+1,tr,max(l,tm+1),r,t);
}
void update(int v,int tl,int tr,
int pos,int new_val,tree *t){
if(tl==tr)
t[v].sum=new_val;
else{
int tm=(tl+tr)/2;
if(pos<=tm)
update(v*2,tl,tm,pos,new_val,t);
else
update(v*2+1,tm+1,tr,pos,new_val,t);
t[v].sum=t[v*2].sum+t[v*2+1].sum;
}
}
int min(int x,int y){
return (x<y)?x:y;
}
int max(int x,int y){
return (x>y)?x:y;
}
int solve(int x,int ancestor){
int ans=0;
while(node_chain[x]!=node_chain[ancestor]){
ans+=sum(1,0,chain_len[node_chain[x]]-1,
0,node_idx[x],chain[node_chain[x]]);