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.

HackerRank Lazy White Falcon problem solution


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;
            this.children = new LinkedList<>();
            this.connections = new LinkedList<>();
        }

        public void addConnection(Node c) {
            this.connections.add(c);
        }

        public void addChild(Node child) {
            this.children.add(child);
            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 SegmentTreeSegmentedAddition rootAggregates;
        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);
            LinkedList<Integer> eulerHeights = new LinkedList<>();
            LinkedList<Node> stack = new LinkedList<>(),
                    eulerPath = new LinkedList<>();
            stack.push(this);
            int depth = 1;
            while(!stack.isEmpty()) {
                Node current = stack.pop();
                eulerPath.add(current);
                eulerHeights.add(depth);
                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() {
            LinkedList<Node> stack = new LinkedList<>();
            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);
                    current.addChild(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;
        }
    }

    class SegmentTreeSegmentedAddition {

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

        public SegmentTreeSegmentedAddition(int[] values) {
            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) {
                tree[v] += add;
            } 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++) {
                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 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) {
        List<Integer> result = new LinkedList<>();
        Node[] nodes = new Node[edges.length + 1];
        for (int i = 0; i < edges.length; i++) {
            int[] link = edges[i];
            int n1 = link[0], n2 = link[1];
            Node node1 = nodes[n1] != null ? nodes[n1] : new Node(n1),
                    node2 = nodes[n2] != null ? nodes[n2] : new Node(n2);
            node1.addConnection(node2);
            node2.addConnection(node1);
            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) {
                    result.add(nodes[arg1].value);
                }
                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;
                    result.add( aggregation );
                }
            }
        }
        
        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],
chain_head[100000],chain_len[100000]={0};
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{
chain_head[cn]=x->x;
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;
chain_head[0]=0;
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]]);
x=DP[0][chain_head[node_chain[x]]];
}
ans+=sum(1,0,chain_len[node_chain[x]]-1,
node_idx[ancestor],node_idx[x],
chain[node_chain[x]]);
return ans;
}