Hackerrank Tree Coordinates problem solution YASH PAL, 31 July 2024 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. Problem solution in 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<Integer>(); 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<Entry>(); 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<Entry>(points.length); List<Entry> list2 = new ArrayList<Entry>(points.length); List<Entry> list3 = new ArrayList<Entry>(points.length); List<Entry> list4 = new ArrayList<Entry>(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(); } } Problem solution in 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 = %dn", ans); printf("%dn", ans); return 0; } Problem solution in 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 <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 <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; } coding problems data structure