HackerRank Heavy Light White Falcon problem solution

YASH PAL,

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.
HackerRank Heavy Light White Falcon problem solution

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

def read_tree(N):
   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())

location = read_tree(N)

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<Integer> result = new LinkedList<>();

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

        // process root
        List<List<Integer>> children = new ArrayList<>();
        boolean[] visited = new boolean[nodes.size()];
        for (int i = 0; i < nodes.size(); i++) {
            children.add(new LinkedList<>());
        }
        LinkedList<Integer> stack = new LinkedList<>();
        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);
                    children.get(current).add(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);
                result.add(maximum);
            }
        }
        return result;
    }
}

class HeavyLightDecompositionTree {

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

    public HeavyLightDecompositionTree(List<List<Integer>> adj) {
        this(adj, new int[adj.size()]);
    }

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

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

        dfs(adj);
        decompose(adj);

        segmentedPos = new SegmentTreeMax(dfsValues);
    }

    private void dfs(List<List<Integer>> adj) {
        boolean[] visited = new boolean[adj.size()];
        int[] weight = new int[adj.size()];
        LinkedList<Integer> stack = new LinkedList<>();
        stack.push(0);
        while (!stack.isEmpty()) {
            int nodeId = stack.pop();
            List<Integer> connections = adj.get(nodeId);
            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;
            }
        }
    }

    private void decompose(List<List<Integer>> adj) {
        int dfsPosition = 0;
        LinkedList<int[]> stack = new LinkedList<>();
        stack.push(new int[]{0,0});
        while (!stack.isEmpty()) {
            int[] e = stack.pop();
            int v = e[0], h = e[1];
            head[v] = h;
            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]) {
                    stack.add(new int[]{c, c});
                }
            }
        }
    }

    public int max(int a, int b) {
        int res = 0;
        for (; head[a] != head[b]; b = parent[head[b]]) {
            if (depth[head[a]] > depth[head[b]]) {
                // swap(a, b);
                int aux = a;
                a = b;
                b = aux;
            }
            int cur_heavy_path_max = segmentedPos.max(dfsPositions[head[b]], dfsPositions[b]);
            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++) {
            this.tree.add(null);
        }
        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 {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        String[] firstMultipleInput = bufferedReader.readLine().replaceAll("\s+$", "").split(" ");

        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 {
                tree.add(
                    Stream.of(bufferedReader.readLine().replaceAll("\s+$", "").split(" "))
                        .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 {
                queries.add(
                    Stream.of(bufferedReader.readLine().replaceAll("\s+$", "").split(" "))
                        .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"
        );

        bufferedReader.close();
        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;
}

vector<int> adj[N];
int n, q;

node* head[N];
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;
    for(int v : adj[u]) {
        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;
        for(int vv : adj[v]) {
            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);
        }
        ans = max(ans, head[G[u]]->query(0, pos[u]));
        u = P[G[u]];
    }
    if(pos[u] > pos[v]) {
        swap(u, v);
    }
    ans = max(ans, head[G[u]]->query(pos[u], pos[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;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    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;
            head[G[u]]->update(pos[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>

typedef struct link {
	struct node1 *with;
	struct link *next;
} link;

typedef struct node1 {
	int id;
	int mark;
	int num_connections;
	link *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;
	struct node *chain_head;
	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;
	while (at && at->chain_head == chain_head) {
		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) {
	if (!chain_head) {
		chain_head = at;
		(*num_chains)++;
	}

	at->chain_head = chain_head;

	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
		build_chain_tree(at, chain_head, chain_length);
	}
}

node * lca(node *u, node *v) {
	while (u->chain_head != v->chain_head) {
		if (u->chain_head->seg.low_depth < v->chain_head->seg.low_depth)
			v = v->chain_head->parent;
		else
			u = u->chain_head->parent;
	}
	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);

	while (lower->chain_head != higher->chain_head) {
		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));
		lower = lower->chain_head->parent;
	}
	//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));
	link *links = (link*)malloc(2 * (n - 1) * sizeof(link));

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

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

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

		link* la = &links[2 * i + 0];
		link* lb = &links[2 * i + 1];

		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;
	free(links); links = NULL;

	//heavy-light decoposition
	int num_chains = 0;
	hld(&processed[0], NULL, 1, &num_chains);
	//printf("made %d chainsn", 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("%dn", val);
		}
	}

	return 0;
}

coding problems data structure