Algorithm
Problem Name: Data Structures -
In this HackerRank in Data Structures -
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;
}
#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;
}
#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();
}
}