Algorithm


Problem Name: Data Structures - Tree Coordinates

Problem Link: https://www.hackerrank.com/challenges/tree-coordinates/problem?isFullScreen=true

In this HackerRank in Data Structures - Tree Coordinates solutions

In this tutorial, we are going to solve or make a solution to the Tree Coordinates problem. so here we have given a tree, T and with n vertices and also given m point. we need to find and print the distance between the two further points in this metric space.

 

Code Examples

#1 Code Example with C Programming

Code - C Programming


#include <stdio.h>
#include <string.h>

void descending(unsigned length, unsigned *weights, unsigned *self) {
    unsigned at, member, node = length >> 1;

    for (self--; node; self[at >> 1] = member) {
        member = self[node];
        for (at = node-- << 1; at  <  length && weights[self[
                 at |= weights[self[at | 1]] < weights[self[at]]
             ]] < weights[member]; 
             at <<= 1
        ) self[at >> 1] = self[at];     

        if (at == length && weights[self[at]]  <  weights[member])
            member ^= self[at], self[at] ^= member, member ^= self[at];
    }
    for (; length > 1; self[at >> 1] = member) {
        member = self[length];
        self[length--] = self[1];
        for (at = 2; at  <  length && weights[self[
                at |= weights[self[at | 1]] < weights[self[at]]
             ]] < weights[member]; 
             at <<= 1
        ) self[at >> 1] = self[at];

        if (at == length && weights[self[at]]  <  weights[member])
            node = self[at], self[at] = member, member = node;
    }
}
// Submitted by Samy Vilar  on 07/07/2019
typedef struct {
    unsigned 
        *weights,
        *depths,        
        *bases,
        *base_indices,
        *ancestral_bases;
} tree_t;

unsigned calc_dist(tree_t *self, unsigned low, unsigned high) {        
    if (high  <  low) 
        low ^= high, high ^= low, low ^= high;

    if (low <= high && high < (low + self->weights[low])) 
        return self->depths[high] - self->depths[low];
        
    unsigned *candidates = &self->ancestral_bases[self->base_indices[self->bases[high]]];
    unsigned short length = self->base_indices[self->bases[high] + 1] - self->base_indices[self->bases[high]];
    
    for (; length > 1; length >>= 1)
        if (candidates[length >> 1]  <  low) {
            candidates += length >> 1;
            length += length & 1;
        }   

    return self->depths[low] + self->depths[high] - (self->depths[*candidates] << 1);
}
// Submitted by Samy Vilar  < samy_vilar> on 07/07/2019
int main() {
    unsigned vertex_cnt, point_cnt;
    scanf("%u %u", &vertex_cnt, &point_cnt);

    unsigned 
        at, others, tail, next,
        ancestors[vertex_cnt];
    
    for (at = vertex_cnt >> 1; at--; ((unsigned long *)ancestors)[at] = 0x100000001UL * vertex_cnt);    
    for (ancestors[at += vertex_cnt] = vertex_cnt; at--; ancestors[others] = tail)
        if (ancestors[(scanf("%u %u", &others, &tail), --tail, --others)] != vertex_cnt)
            for (next = tail, tail = others, others = next; ancestors[others] != vertex_cnt; others = next) {
                next = ancestors[others];
                ancestors[others] = tail;
                tail = others;
            }    

    unsigned
        indices[vertex_cnt + 2],
        descendants[vertex_cnt];                       

    memset(indices, 0, sizeof(indices));
    for (at = vertex_cnt; at--; *(unsigned long *)&indices[ancestors[at]] += 0x100000001UL);
    for (; ++at  <  (vertex_cnt >> 1); ((unsigned long *)indices)[at + 1] += ((unsigned long *)indices)[at]);        
    for (at = vertex_cnt; at--; descendants[--indices[ancestors[at]]] = at);
        
    unsigned 
        history[vertex_cnt],
        weights[vertex_cnt + 1];

    at += vertex_cnt;
    for (history[at] = descendants[at], tail = 0; tail  <  at; tail++) {        
        history[tail] = history[at];
        at -= (indices[history[tail] + 1] - indices[history[tail]]) - 1;
        memcpy(
            &history[at], 
            &descendants[indices[history[tail]]], 
            (indices[history[tail] + 1] - indices[history[tail]]) * sizeof(history[0])
        );
    }        
    for (at = vertex_cnt >> 1; at--; ((unsigned long *)weights)[at] = 0x100000001UL);
    for (*(unsigned long *)&weights[(at = vertex_cnt) - 1] = 1UL; --at; 
        weights[ancestors[history[at]]] += weights[history[at]]);    

    unsigned        
        depths[vertex_cnt],
        bases[vertex_cnt],
        ids[vertex_cnt + 1],
        base_indices[vertex_cnt + 1];    

    memcpy(bases, weights, vertex_cnt * sizeof(weights[0]));
    
    weights[0] = vertex_cnt;                        
    for (ids[history[0]] = (depths[0] = (at = 0)); at  <  tail; at++) {
        others = indices[history[at]];
        descending(indices[history[at] + 1] - others, bases, &descendants[others]);                                    
        for (next = ids[history[at]] + 1; others  <  indices[history[at] + 1]; next += weights[next]) {
            ids[descendants[others]] = next;            
            ancestors[next] = ids[history[at]];                        
            depths[next] = depths[ancestors[next]] + 1;
            weights[next] = bases[descendants[others++]];
        }        
    }        
    
    memset(base_indices, 0, sizeof(base_indices));        
    for (bases[0] = (at = 0); ++at  <  vertex_cnt; ) 
        if ((ancestors[at] + 1) == at)
            bases[at] = bases[ancestors[at]];
        else 
            base_indices[(bases[at] = at) + 1] = base_indices[bases[ancestors[at]] + 1] + 1;        
        
    for (at = 0; ++at  <  vertex_cnt; base_indices[at] += base_indices[at - 1]);
    base_indices[at] += base_indices[at - 1];

    unsigned ancestral_bases[base_indices[at]];
    for (others = base_indices[at--]; others; at--)
        if (base_indices[at]  <  others) 
            for (ancestral_bases[--others] = ancestors[at]; others > base_indices[at]; others--)
                ancestral_bases[others - 1] = ancestors[bases[ancestral_bases[others]]];         

    unsigned 
        x_points[point_cnt],
        y_points[point_cnt];
    
    for (at = point_cnt; at--; x_points[at] = ids[x_points[at] - 1]) {
        scanf("%u %u", &x_points[at], &y_points[at]);                
        y_points[at] = ids[y_points[at] - 1];
    }

    memset(indices, 0, sizeof(indices));
    for (at = vertex_cnt; --at; *(unsigned long *)&indices[ancestors[at]] += 0x100000001UL);
    for (; ++at  < = (vertex_cnt >> 1); ((unsigned long *)indices)[at] += ((unsigned long *)indices)[at - 1]);
    for (at = vertex_cnt; --at; descendants[--indices[ancestors[at]]] = at);

    // Submitted by Samy Vilar  < samy_vilar> on 07/07/2019

    unsigned mass[vertex_cnt + 1];
    {
        unsigned 
            centroids[vertex_cnt],
            id = 0;

        ancestors[0] = (centroids[0] = (mass[0] = vertex_cnt));
        for (history[0] = 0, at = 1; at--; weights[next] = 0, ids[next] = id++) {
            for (tail = (next = history[at]); (weights[next] << 1)  <  mass[history[at]]; next = ancestors[tail = next]);
            for (others = indices[next]; others  <  indices[next + 1]; others++)
                if ((weights[descendants[others]] << 1) > mass[history[at]] && descendants[others] != tail)
                    others = indices[next = descendants[others]] - 1;

            centroids[next] = centroids[history[at]];                   
            for (mass[next] = mass[history[at]]; others-- > indices[next]; )
                if (weights[descendants[others]]) {                                      
                    centroids[history[at] = descendants[others]] = next;                                        
                    mass[history[at++]] = weights[descendants[others]];
                }      

            for (others = next; weights[ancestors[others]]; weights[others = ancestors[others]] -= weights[next]);        
            if (others != next) {
                centroids[history[at] = ancestors[next]] = next;                
                mass[history[at++]] = weights[others];
            }
        }       
        for (at = vertex_cnt >> 1; at--; ((unsigned long *)weights)[at] = 0x100000001UL);
        for (weights[(at = vertex_cnt) - 1] = 1; --at; weights[ancestors[at]] += weights[at]);            
                    
        memset(indices, 0, sizeof(indices));
        for (at = vertex_cnt; at--; *(unsigned long *)&indices[centroids[at]] += 0x100000001UL);
        for (; ++at  <  (vertex_cnt >> 1); ((unsigned long *)indices)[at + 1] += ((unsigned long *)indices)[at]);        
        for (at = vertex_cnt; at--; descendants[--indices[centroids[at]]] = at);        
        memcpy(ancestors, centroids, vertex_cnt * sizeof(centroids[0]));
    }    

    unsigned x_indices[vertex_cnt + 2];
    {                        
        unsigned buffers[2][point_cnt];

        memset(x_indices, 0, sizeof(x_indices));
        for (at = point_cnt; at--; *(unsigned long *)&x_indices[ids[x_points[at]]] += 0x100000001UL);
        for (; ++at  <  (vertex_cnt >> 1); ((unsigned long *)x_indices)[at + 1] += ((unsigned long *)x_indices)[at]);                    
        for (at = point_cnt; at--; buffers[1][x_indices[ids[x_points[at]]]] = y_points[at])
            buffers[0][--x_indices[ids[x_points[at]]]] = x_points[at];         

        memcpy(x_points, buffers[0], sizeof(x_points));
        memcpy(y_points, buffers[1], sizeof(y_points));
    }
    
    // Submitted by Samy Vilar  < samy_vilar> on 07/07/2019    

    tree_t *tree_props = &(tree_t) {
        .weights = weights,
        .depths = depths,        
        .bases = bases,
        .base_indices = base_indices,
        .ancestral_bases = ancestral_bases
    };

    union path_t {
        unsigned long packd;
        struct {
            unsigned branch;
            int dist;
        };
    } furthest[vertex_cnt],
      second[vertex_cnt],
      candidate;
            
    for (at = vertex_cnt; at--; furthest[at].packd = 0x8000000000000000UL | vertex_cnt);        
    memcpy(second, furthest, sizeof(furthest));
    
    // Submitted by Samy Vilar  < samy_vilar> on 07/07/2019

    int max_seen = 0; 
    
    mass[ids[vertex_cnt] = vertex_cnt] = 0;
    ancestors[descendants[vertex_cnt - 1]] = 0xFFFFFFFFU;    
    
    unsigned x_dist, at_x = vertex_cnt;

    while (at_x--) {                                
        for (others = x_indices[ids[at_x] + mass[at_x]]; others-- > x_indices[ids[at_x]]; ) 
            for (tail = y_points[others]; tail != 0xFFFFFFFFU && furthest[tail].dist != 0x80000000U; tail = ancestors[tail]) 
                second[tail].packd = (furthest[tail].packd = vertex_cnt | 0x8000000000000000UL);                
            
        while (++others  <  x_indices[ids[at_x] + 1])
            for (next = y_points[others], candidate.branch = vertex_cnt; next != 0xFFFFFFFFU; next = ancestors[candidate.branch = next]) {
                candidate.dist = calc_dist(tree_props, next, y_points[others]);                

                if ((ids[candidate.branch]  <   ids[furthest[next].branch] || 
                     ids[candidate.branch] >= (ids[furthest[next].branch] + mass[furthest[next].branch]))
                        && max_seen < (candidate.dist + furthest[next].dist))                          
                    max_seen = candidate.dist + furthest[next].dist;
                else if ((ids[candidate.branch] < ids[second[next].branch] || 
                          ids[candidate.branch] >= (ids[second[next].branch] + mass[second[next].branch]))
                            && max_seen < ((candidate.dist + second[next].dist)))
                    max_seen = candidate.dist + second[next].dist;        
                
                if (furthest[next].dist  <  candidate.dist) {
                    if (furthest[next].branch != candidate.branch) 
                        second[next].packd = furthest[next].packd;

                    furthest[next].packd = candidate.packd;                    
                } else if (second[next].dist  <  candidate.dist && furthest[next].branch != candidate.branch) 
                    second[next].packd = candidate.packd;                
            }                                          
           
        // Submitted by Samy Vilar  on 07/07/2019

        for (others = indices[at_x]; others  <  indices[at_x + 1]; others++) {
            for (at = x_indices[ids[descendants[others]]]; 
                 at  <  x_indices[ids[descendants[others]] + mass[descendants[others]]]; 
                 at++
            ) {
                x_dist = calc_dist(tree_props, at_x, x_points[at]);                 

                for (next = y_points[at], tail = vertex_cnt; next != 0xFFFFFFFFU; next = ancestors[tail = next])
                    if (ids[tail]  <    ids[furthest[next].branch] || 
                        ids[tail] >= (ids[furthest[next].branch] + mass[furthest[next].branch])) 
                    {                
                        candidate.dist = furthest[next].dist + x_dist + calc_dist(tree_props, next, y_points[at]);
                        if (max_seen < candidate.dist)
                            max_seen = candidate.dist;
                    } else if (ids[tail]  <    ids[second[next].branch] || 
                               ids[tail] >= (ids[second[next].branch] + mass[second[next].branch])) 
                    {                    
                        candidate.dist = second[next].dist + x_dist + calc_dist(tree_props, next, y_points[at]);
                        if (max_seen < candidate.dist)
                            max_seen = candidate.dist;
                    }
            }            
            while (at-- > x_indices[ids[descendants[others]]]) {
                x_dist = calc_dist(tree_props, at_x, x_points[at]);   

                candidate.branch = vertex_cnt;
                for (next = y_points[at]; next != 0xFFFFFFFFU; next = ancestors[candidate.branch = next]) {
                    candidate.dist = x_dist + calc_dist(tree_props, next, y_points[at]);                    

                    if (furthest[next].dist  <  candidate.dist) {
                        if (furthest[next].branch != candidate.branch) 
                            second[next].packd = furthest[next].packd;                            
                                                
                        furthest[next].packd = candidate.packd;                        
                    } else if (second[next].dist  <  candidate.dist && furthest[next].branch != candidate.branch) 
                        second[next].packd = candidate.packd;                    
                }            
            }
        }
    }
    
    printf("%u", max_seen);
    return 0;
}
Copy The Code & Try With Live Editor

#2 Code Example with C++ Programming

Code - C++ Programming


#include <iostream>
#include <fstream>
#include <sstream>
 
#include <vector>
#include <set>
#include <bitset>
#include <map>
#include <deque>
#include <string>
 
#include <algorithm>
#include <numeric>
 
#include <cstdio>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
 
#define pb push_back
#define pbk pop_back
#define mp make_pair
#define fs first
#define sc second
#define all(x) (x).begin(), (x).end()
#define foreach(i, a) for (__typeof((a).begin()) i = (a).begin(); i != (a).end(); ++i)
#define len(a) ((int) (a).size())
 
#ifdef CUTEBMAING
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define eprintf(...) 42
#endif
 
using namespace std;
 
typedef long long int64;
typedef long double ld;
typedef unsigned long long lint;
 
const int inf = (1 << 30) - 1;
const int64 linf = (1ll << 62) - 1;
const int N = 1e5 + 100;
const int K = 17;
 
struct layer {
	int color[N], root[N];
	int dist[N];
	pair < int, int> max1[N], max2[N];
 
	layer() {
		fill_n(color, N, -1);
		fill_n(root, N, -1);
		fill_n(dist, N, -1);
		fill_n(max1, N, mp(-inf, -inf));
		fill_n(max2, N, mp(-inf, -inf));
	}
};
 
int n, m;
vector < vector<int>> g, backup;
int reqA[N], reqB[N];
 
layer st[K];
 
int comp[N], compLen = 0;
int parent[N], size[N];
 
inline void update(pair < int, int> &a, pair<int, int> &b, const pair<int, int> &c) {
	if (a.fs < c.fs) {
		if (a.sc != c.sc) {
			b = a;
		}
		a = c;
	} else if (b.fs  <  c.fs && c.sc != a.sc) {
		b = c;
	}
}
 
inline void update(int v, int value) {
	for (int i = 0; i  <  K; i++) {
		layer &layer = st[i];
		int root = layer.root[v];
		if (root == -1) {
			break;
		}
		update(layer.max1[root], layer.max2[root], mp(value + layer.dist[v], layer.color[v]));
	}
}
 
inline int getValue(int v) {
	int ans = -inf;
	for (int i = 0; i  <  K; i++) {
		layer &layer = st[i];
		int root = layer.root[v];
		if (root == -1) {
			break;
		}
		if (layer.max1[root].sc != layer.color[v] || layer.max1[root].sc == -1) {
			ans = max(ans, layer.max1[root].fs + layer.dist[v]);
		} else if (layer.max2[root].sc != layer.color[v] || layer.max2[root].sc == -1) {
			ans = max(ans, layer.max2[root].fs + layer.dist[v]);
		}
	}
	return ans;
}
 
inline int dfsSize(int v, int p = -1) {
	size[v] = 1;
	comp[compLen++] = v;
	parent[v] = p;
	for (int to : g[v]) {
		if (to != p) {
			size[v] += dfsSize(to, v);
		}
	}
	return size[v];
}
 
inline int findRoot(int v) {
	compLen = 0;
	int total = dfsSize(v);
	for (int i = 0; i  <  compLen; i++) {
		v = comp[i];
		bool flag = true;
		if ((total - size[v]) * 2 > total) {
			continue;
		}
		for (int j : g[v]) {
			if (j != parent[v] && size[j] * 2 > total) {
				flag = false;
				break;
			}
		}
		if (flag) {
			return v;
		}
	}
	assert(false);
}
 
inline void dfsColor(layer &layer, int v, int root, int color, int d = 1, int p = -1) {
	layer.color[v] = color;
	layer.root[v] = root;
	layer.dist[v] = d;
	for (int to : g[v]) {
		if (to != p) {
			dfsColor(layer, to, root, color, d + 1, v);
		}
	}
}
 
inline void buildDivideAndConquer(int x, int v) {
	layer &layer = st[x];
	v = findRoot(v);
	for (int to : g[v]) {
		g[to].erase(find(all(g[to]), v));
	}
	layer.color[v] = -1;
	layer.root[v] = v;
	layer.dist[v] = 0;
	for (int to : g[v]) {
		dfsColor(layer, to, v, to);
	}
	for (int to : g[v]) {
		buildDivideAndConquer(x + 1, to);
	}
}
 
int ans = -inf;
 
int color[N], dist[N];
 
inline void dfsColor2(int v, int c, int d = 1, int p = -1) {
	color[v] = c;
	dist[v] = d;
	for (int to : g[v]) {
		if (to != p) {
			dfsColor2(to, c, d + 1, v);
		}
	}
}
 
inline void clearUpdate(int v) {
	for (int i = 0; i  <  K; i++) {
		if (st[i].root[v] == -1) {
			break;
		}
		st[i].max1[st[i].root[v]].fs = -inf;
		st[i].max2[st[i].root[v]].fs = -inf;
	}
}
 
inline void divideAndConquer(int v, vector<int> requests) {
	v = findRoot(v);
	for (int to : g[v]) {
		g[to].erase(find(all(g[to]), v));
	}
	color[v] = -1, dist[v] = 0;
	for (int i = 0; i  <  len(g[v]); i++) {
		int to = g[v][i];
		dfsColor2(to, i);
	}
	vector < vector<int>> req(len(g[v]));
	for (int i : requests) {
		if (reqA[i] == v) {
			ans = max(ans, getValue(reqB[i]));
			update(reqB[i], 0);
		} else {
			req[color[reqA[i]]].pb(i);
		}
	}
	for (const auto &subtree : req) {
		for (int j : subtree) {
			ans = max(ans, getValue(reqB[j]) + dist[reqA[j]]);
		}
		for (int j : subtree) {
			update(reqB[j], dist[reqA[j]]);
		}
	}
	for (int i : requests) {
		clearUpdate(reqB[i]);
	}
	for (int i = 0; i  <  len(g[v]); i++) {
		int to = g[v][i];
		divideAndConquer(to, req[i]);
	}
}
 
int main() {
	cerr << sizeof(st) / 1024 / 1024 << endl;
	cin >> n >> m;
	g.resize(n);
	for (int i = 0; i  <  n - 1; i++) {
		int u, v; scanf("%d%d", &u, &v), u--, v--;
		g[u].pb(v);
		g[v].pb(u);
	}
	backup = g;
	for (int i = 0; i  <  m; i++) {
		scanf("%d%d", &reqA[i], &reqB[i]), reqA[i]--, reqB[i]--;
	}
	buildDivideAndConquer(0, 0);
	g = backup;
	vector<int> req(m);
	for (int i = 0; i  <  m; i++) {
		req[i] = i;
	}
	divideAndConquer(0, req);
	eprintf("ans = %d\n", ans);
	printf("%d\n", ans);
    return 0;
}
Copy The Code & Try With Live Editor

#3 Code Example with Java Programming

Code - Java Programming


import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;

class Entry implements Comparable < Entry> {
    int x;
    int y;
    int val;
    public Entry(int x, int y, int val) {
        this.x = x;
        this.y = y;
        this.val = val;
    }
    public int compareTo(Entry other) {
        return val - other.val;
    }
}

public class Solution {

static int[][] buildSparseTable(int[] arr) {
        int pow = 1;
        while ((1 << pow)  <  arr.length) pow++;
        int[][] result = new int[arr.length][pow];
        for (int i = 0; i  <  arr.length; i++) result[i][0] = arr[i];
        for (int j = 1; j  < = pow; j++) {
            for (int i = 0; i + (1 << j)  < = arr.length; i++) {
                result[i][j] = Math.min(result[i][j-1],
                                        result[i + (1 << (j-1))][j-1]);
            }
        }
        return result;
    }    /*
     * Complete the treeCoordinates function below.
     */
static int treeCoordinates(int n, int[][] edges, int[][] points) {
        ArrayList < Integer>[] nodes = new ArrayList[n + 1];
        for (int i = 1; i  < = n; i++) nodes[i] = new ArrayList();
        for (int[] edge : edges) {
            nodes[edge[0]].add(edge[1]);
            nodes[edge[1]].add(edge[0]);
        }

        // Find diameter (two BFS)
        int root = 0;
        int tail = 0;
        {
            class Entry {
                int node;
                int dist;
                public Entry(int node, int dist) {
                    this.node = node;
                    this.dist = dist;
                }
            }
            LinkedList < Entry> Q = new LinkedList();
            boolean[] visited = new boolean[n + 1];
            visited[1] = true;
            Q.offer(new Entry(1, 0));
            int maxDist = 0;
            int farNode = 1;
            while (Q.size() > 0) {
                Entry cur = Q.poll();
                if (cur.dist > maxDist) {
                    maxDist = cur.dist;
                    farNode = cur.node;
                }
                for (int neighbor : nodes[cur.node]) {
                    if (visited[neighbor]) continue;
                    visited[neighbor] = true;
                    Q.offer(new Entry(neighbor, cur.dist + 1));
                }
            }
            root = farNode;
            
            Q = new LinkedList  <  Entry > ();
            visited = new boolean[n + 1];
            visited[root] = true;
            Q.offer(new Entry(root, 0));
            maxDist = 0;
            farNode = root;
            while (Q.size() > 0) {
                Entry cur = Q.poll();
                if (cur.dist > maxDist) {
                    maxDist = cur.dist;
                    farNode = cur.node;
                }
                for (int neighbor : nodes[cur.node]) {
                    if (visited[neighbor]) continue;
                    visited[neighbor] = true;
                    Q.offer(new Entry(neighbor, cur.dist + 1));
                }
            }
            tail = farNode;
        }
        //System.out.println("root = " + root + ", tail = " + tail);

        // Euler tour
        int[] eulerTour = new int[2*n - 1];
        final int[] depth = new int[n + 1];
        int[] eulerLevels = new int[2*n - 1];
        int[] eulerIndex = new int[n + 1];
        boolean[] visited = new boolean[n + 1];
        
        int[] S = new int[n];
        int spos = 0;
        S[0] = root;
        int pos = 0;
        int[] neighborCount = new int[n + 1];
        while (spos > -1) {
            int cur = S[spos--];
            if (!visited[cur]) {
                depth[cur] = spos + 1;
                eulerIndex[cur] = pos;
                visited[cur] = true;
            }
            eulerLevels[pos] = spos + 1;
            eulerTour[pos] = cur;
            pos++;
            while (neighborCount[cur]  <  nodes[cur].size()) {
                if (visited[nodes[cur].get(neighborCount[cur])]) {
                    neighborCount[cur]++;
                    continue;
                }
                int next = nodes[cur].get(neighborCount[cur]);
                //parent[next] = cur;
                S[++spos] = cur;
                S[++spos] = next;
                neighborCount[cur]++;
                break;
            }
        }

        int[][] lookup = buildSparseTable(eulerLevels);

        List < Entry> list1 = new ArrayList(points.length);
        List list2 = new ArrayList(points.length);
        List < Entry> list3 = new ArrayList(points.length);
        List list4 = new ArrayList(points.length);

        for (int i = 0; i  <  points.length; i++) {
            int x = points[i][0];
            int y = points[i][1];
            int xLcaLevel;
            {
                int start = Math.min(eulerIndex[x], eulerIndex[tail]);
                int end = Math.max(eulerIndex[x], eulerIndex[tail]);
                int pow = 0;
                while (1 << (pow + 1)  < = (end - start)) pow++;
                xLcaLevel = Math.min(lookup[start][pow],   
                                     lookup[end + 1 - (1 << pow)] [pow]);
            }
            int yLcaLevel;
            {
                int start = Math.min(eulerIndex[y], eulerIndex[tail]);
                int end = Math.max(eulerIndex[y], eulerIndex[tail]);
                int pow = 0;
                while (1 << (pow + 1)  < = (end - start)) pow++;
                yLcaLevel = Math.min(lookup[start][pow],   
                                     lookup[end + 1 - ( 1 << pow)] [pow]);
            }
            int val1 = depth[x] + depth[y];
            list1.add(new Entry(x, y, val1));
            int val2 = -depth[x] - depth[y] + 2*xLcaLevel + 2*yLcaLevel;
            list2.add(new Entry(x, y, val2));
            int val3 = depth[x] + depth[y] - 2*xLcaLevel;
            list3.add(new Entry(x, y, val3));
            int val4 = -depth[x] - depth[y] + 2*yLcaLevel;
            list4.add(new Entry(x, y, val4));
        }
        Collections.sort(list1, Collections.reverseOrder());
        Collections.sort(list2);
        Collections.sort(list3, Collections.reverseOrder());
        Collections.sort(list4);

        int maxDist = 0;

        for (int i = 0; i  <  points.length; i++) {
            boolean shouldContinue = false;
            for (int j = 0; j  < = i; j++) {
                Entry e1 = list1.get(i-j);
                Entry e2 = list2.get(j);
                int potential12 = e1.val - e2.val;
                if (potential12 > maxDist) {
                    shouldContinue = true;
                    int x1 = e1.x;
                    int y1 = e1.y;
                    int x2 = e2.x;
                    int y2 = e2.y;
                    int xLcaLevel;
                    {
                        int start = Math.min(eulerIndex[x1], eulerIndex[x2]);
                        int end = Math.max(eulerIndex[x1], eulerIndex[x2]);
                        int pow = 0;
                        while (1 << (pow + 1)  < = (end - start)) pow++;
                        xLcaLevel = Math.min(lookup[start][pow],   
                                             lookup[end + 1 - (1<<pow)][pow]);
                    }
                    int yLcaLevel;
                    {
                        int start = Math.min(eulerIndex[y1], eulerIndex[y2]);
                        int end = Math.max(eulerIndex[y1], eulerIndex[y2]);
                        int pow = 0;
                        while (1 << (pow + 1)  < = (end - start)) pow++;
                        yLcaLevel = Math.min(lookup[start][pow],   
                                             lookup[end + 1 - (1<< pow)][pow]);
                    }
                    int actual12 = depth[x1] + depth[x2] - 2*xLcaLevel
                                   + depth[y1] + depth[y2] - 2*yLcaLevel;
                    maxDist = Math.max(maxDist, actual12);
                }
                Entry e3 = list3.get(i-j);
                Entry e4 = list4.get(j);
                int potential34 = e3.val - e4.val;
                if (potential34 > maxDist) {
                    shouldContinue = true;
                    int x3 = e3.x;
                    int y3 = e3.y;
                    int x4 = e4.x;
                    int y4 = e4.y;
                    int xLcaLevel;
                    {
                        int start = Math.min(eulerIndex[x3], eulerIndex[x4]);
                        int end = Math.max(eulerIndex[x3], eulerIndex[x4]);
                        int pow = 0;
                        while (1 << (pow + 1)  < = (end - start)) pow++;
                        xLcaLevel = Math.min(lookup[start][pow],   
                                             lookup[end + 1 - (1 << pow)][pow]);
                    }
                    int yLcaLevel;
                    {
                        int start = Math.min(eulerIndex[y3], eulerIndex[y4]);
                        int end = Math.max(eulerIndex[y3], eulerIndex[y4]);
                        int pow = 0;
                        while (1 << (pow + 1)  < = (end - start)) pow++;
                        yLcaLevel = Math.min(lookup[start][pow],   
                                             lookup[end + 1 - (1 << pow)][pow]);
                    }
                    int actual34 = depth[x3] + depth[x4] - 2*xLcaLevel
                                   + depth[y3] + depth[y4] - 2*yLcaLevel;
                    maxDist = Math.max(maxDist, actual34);
                }
            }
            if (!shouldContinue) break;
        }

        return maxDist;
    }

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

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

        int m = Integer.parseInt(nm[1].trim());

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

        for (int edgesRowItr = 0; edgesRowItr  <  n-1; edgesRowItr++) {
            String[] edgesRowItems = scanner.nextLine().split(" ");

            for (int edgesColumnItr = 0; edgesColumnItr  <  2; edgesColumnItr++) {
                int edgesItem = Integer.parseInt(edgesRowItems[edgesColumnItr].trim());
                edges[edgesRowItr][edgesColumnItr] = edgesItem;
            }
        }

        int[][] points = new int[m][2];

        for (int pointsRowItr = 0; pointsRowItr  <  m; pointsRowItr++) {
            String[] pointsRowItems = scanner.nextLine().split(" ");

            for (int pointsColumnItr = 0; pointsColumnItr  <  2; pointsColumnItr++) {
                int pointsItem = Integer.parseInt(pointsRowItems[pointsColumnItr].trim());
                points[pointsRowItr][pointsColumnItr] = pointsItem;
            }
        }

        int result = treeCoordinates(n, edges, points);

        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();

        bufferedWriter.close();
    }
}
Copy The Code & Try With Live Editor
Advertisements

Demonstration


Previous
[Solved] Jenny's Subtrees solution in Hackerrank - Hacerrank solution C, C++, java,js, Python
Next
[Solved] Array Pairs solution in Hackerrank - Hacerrank solution C, C++, java,js, Python