Algorithm
Problem Name: Data Structures -
https://www.hackerrank.com/challenges/ab0/problem?isFullScreen=true
In this HackerRank in Data Structures -
Burger Town is a city that consists of N special junctions and N - 1 pathways. There is exactly one shortest path between each pair of junctions. Junction i is located at (xi,yi) and the distance between two junctions i,j is defined by the Taxicab geometry.
Tim has recently afforded a taxicab to work as a taxicab driver. His vehicle was very cheap, but has a very big flaw. It can only drive H units horizontally and V units vertically before refueling.
If a customer wants to be brought from a junction i to another junction j then this car is only capable of driving the route, iff the sum of horizontal distances and the sum of vertical distances on this path are less than or equal to H and V respectively.
Also, there is a unique path between any two junctions.
Now he has thoughts about returning the vehicle back to the seller. But he first wants to know, if it's even worth it. That's why he wants to know the number of unordered pairs (i,j) such that it is not possible to drive a customer from junction i to junction j.
Input Format
On the first line you will be given N,H and V separated by a single space.
Each of the next N lines contains two space separated integers xi,yi denoting the location of junction i. Each of the next N - 1 lines contains two space separated integers describing a path existing between ui,vi , i.e., there is a path between ui and vi.
Output Format
Output the number of unordered pairs (i,j) such that it is not possible to drive from i to j.
Constraints
2 <= N <= 10**5
0 <= H,V <= 10**14
0 <= xi, yi <= 10**9
Sample Input
3 2 1
0 0
1 1
2 0
1 2
2 3
Sample Output
1
Explanation
The car is only capable of driving H = 2 units horizontally and V = 1 unit vertically. The horizontal distance between junction 1 and 3(via 2) is equal to 2(0 -> 1 -> 2), which fits under the horizontal limit of the car. The vertical distance between 1 and 3 is also equal to 2(0 -> 1 -> 2), but this is not possible for this car since 2 > V
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define have(self, id) ((self)[(id) >> 5] & (1U << ((id) & 31U)))
#define inv(self, id) ((self)[(id) >> 5] ^= (1U << ((id) & 31U)))
static inline unsigned delta(unsigned self, unsigned other) {
return (self < other) ? (other - self) : (self - other);
}
void ascending_stbl(unsigned length, unsigned long *weights, unsigned *self) {
unsigned
at, span,
at_left, at_right,
*left, *right,
order[length];
for (span = 1; span < length; span <<= 1)
for (left = &((unsigned *)memcpy(order, self, sizeof(order[0]) * length))[at = length]; at > span; ) {
right = left - (at_right = span);
at_left = (at < (span << 1)) ? (at - span) : span;
for (left -= at_left + at_right; at_left && at_right;
self[--at] = (weights[left[at_left - 1]] > weights[right[at_right - 1]])
? left[--at_left] : right[--at_right]);
memcpy(&self[at -= (at_left | at_right)], right, at_right * sizeof(self[0]));
}
}
int main() {
unsigned vertex_cnt;
unsigned long limits[2];
scanf("%u %lu %lu", &vertex_cnt, &limits[0], &limits[1]);
unsigned
cords[2][vertex_cnt],
neighbors[vertex_cnt << 1],
ancestors[vertex_cnt],
indices[vertex_cnt + 2],
next, tail, others, at;
for (at = 0; at < vertex_cnt; at++)
scanf("%u %u", &cords[0][at], &cords[1][at]);
for (at >>= 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", &tail, &others), --tail, --others)] != vertex_cnt)
for (tail ^= others, others ^= tail, tail ^= others;
ancestors[others] != vertex_cnt;
others = next
) {
next = ancestors[others];
ancestors[others] = tail;
tail = others;
}
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--; neighbors[--indices[ancestors[at]]] = at);
unsigned
history[vertex_cnt],
weights[vertex_cnt + 1];
at += vertex_cnt;
history[at] = neighbors[at];
for (others = 0; others < at; others++) {
history[others] = history[at];
at -= (indices[history[at] + 1] - indices[history[at]]) - 1U;
memcpy(
&history[at],
&neighbors[indices[history[others]]],
sizeof(history[0]) * (indices[history[others] + 1] - indices[history[others]])
);
}
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
offsets[vertex_cnt + 2],
forward[vertex_cnt];
{
unsigned
mass[vertex_cnt],
centroids[vertex_cnt];
centroids[history[0]] = (mass[0] = vertex_cnt);
for (at = 1; at--; weights[next] = 0) {
for (others = (tail = history[at]); (weights[others] << 1) < mass[at]; others = ancestors[tail = others]);
for (others = indices[next = others]; others < indices[next + 1]; others++)
if ((weights[neighbors[others]] << 1) > mass[at] && neighbors[others] != tail)
others = indices[next = neighbors[others]] - 1;
for (centroids[next] = centroids[history[at]]; others-- > indices[next]; )
if (weights[neighbors[others]]) {
centroids[history[at] = neighbors[others]] = next;
mass[at++] = weights[neighbors[others]];
}
for (others = next; weights[ancestors[others]]; weights[others = ancestors[others]] -= weights[next]);
if (others != next) {
centroids[history[at] = ancestors[next]] = next;
mass[at++] = weights[others];
}
}
memset(offsets, 0, sizeof(offsets));
for (at = vertex_cnt; at--; *(unsigned long *)&offsets[centroids[at]] += 0x100000001UL);
for (; ++at < (vertex_cnt >> 1); ((unsigned long *)offsets)[at + 1] += ((unsigned long *)offsets)[at]);
for (at = vertex_cnt; at--; forward[--offsets[centroids[at]]] = at);
}
for (at = forward[(tail = vertex_cnt) - 1]; at != vertex_cnt; at = next) {
next = ancestors[at];
ancestors[at] = tail;
tail = at;
}
for (at >>= 1; at--; ((unsigned long *)indices)[at] = 0x200000002UL);
*(unsigned long *)indices = 0x200000001UL;
for (*(unsigned long *)&indices[(at = vertex_cnt) - 1] = 0x100000002UL; 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--; neighbors[--indices[ancestors[at]]] = at);
for (; ++at < vertex_cnt; neighbors[--indices[at]] = ancestors[at]);
indices[at + 1] = at << 1;
unsigned
ordered[vertex_cnt << 1],
ranks[vertex_cnt << 1],
sums[vertex_cnt << 1],
deltas[2][vertex_cnt],
seen[((vertex_cnt + 1) >> 5) + 1];
unsigned long
total = 0,
max[2],
(*dists)[2][vertex_cnt << 1] = malloc(sizeof(dists[0]));
memset(seen, 0, sizeof(seen));
inv(seen, at);
for (history[0] = forward[at - 1], at = 1; at--; ) {
inv(seen, history[at]);
dists[0][0][vertex_cnt + history[at]] = (dists[0][1][vertex_cnt + history[at]] = (max[0] = (max[1] = 0UL)));
for (history[tail = vertex_cnt - 1] = history[next = at]; tail < vertex_cnt; next++)
for (others = indices[(history[next] = history[tail++]) + 1]; others-- > indices[history[next]]; )
if (have(seen, neighbors[others]) == 0) {
inv(seen, neighbors[others]);
weights[history[--tail] = neighbors[others]] = 1;
ordered[history[tail]] = history[next];
dists[0][0][vertex_cnt + history[tail]] = dists[0][0][vertex_cnt + history[next]]
+ delta(cords[0][history[next]], cords[0][history[tail]]);
dists[0][1][vertex_cnt + history[tail]] = dists[0][1][vertex_cnt + history[next]]
+ delta(cords[1][history[next]], cords[1][history[tail]]);
if (max[0] < dists[0][0][vertex_cnt + history[tail]])
max[0] = dists[0][0][vertex_cnt + history[tail]];
if (max[1] < dists[0][1][vertex_cnt + history[tail]])
max[1] = dists[0][1][vertex_cnt + history[tail]];
}
if ((max[0] << 1) < = limits[0] && (max[1] << 1) < = limits[1])
continue ;
for (weights[history[at]] = 1; --next > at; inv(seen, history[next]))
weights[ordered[history[next]]] += weights[history[next]];
ranks[history[next++]] = 0;
for (tail = 1, others = next; others < (at + weights[history[at]]); )
for (next += weights[history[next]], max[0] = tail; others < next; )
if (dists[0][0][vertex_cnt + history[others]] > limits[0]
|| dists[0][1][vertex_cnt + history[others]] > limits[1]) {
total += (max[0] + ((at + weights[history[at]]) - next)) * weights[history[others]];
others += weights[history[others]];
} else {
ancestors[ranks[history[others]] = tail] = ranks[ordered[history[others]]];
dists[0][0][tail] = dists[0][0][vertex_cnt + history[others]];
dists[0][1][tail++] = dists[0][1][vertex_cnt + history[others++]];
}
for (others = tail >> 1; others--; ((unsigned long *)weights)[others] = 0x100000001UL);
for (weights[(others = tail) - 1] = 1; --others; weights[ancestors[others]] += weights[others]) {
dists[0][0][tail + others] = limits[0] - dists[0][0][others];
dists[0][1][tail + others] = limits[1] - dists[0][1][others];
ordered[others - 1] = others;
ordered[tail + others - 2] = tail + others;
}
others = (tail - 1) << 1;
for (ascending_stbl(others, dists[0][1], ordered); others--; ranks[ordered[others]] = others);
for (; ++others < (tail - 1); ordered[others] = others + 1)
ordered[tail + others - 1] = tail + others + 1;
ascending_stbl((others <<= 1), dists[0][0], ordered);
memset(sums, 0, others * sizeof(sums[0]));
for (tail = 0; tail < others; tail++)
if (ordered[tail] > weights[0]) {
deltas[0][ordered[tail] -= weights[0]] = 0;
for (next = ranks[ordered[tail] + weights[0]]; next != 0xFFFFFFFFU; next = (next & (next + 1)) - 1)
deltas[0][ordered[tail]] += sums[next];
ordered[tail] += weights[0];
} else
for (next = ranks[ordered[tail]]; next < others; next |= next + 1)
sums[next]++;
unsigned long sum = 0;
deltas[0][0] = weights[0] - 1;
for (others = 1; others < weights[0]; ) {
for (tail = weights[others]; tail--; ordered[tail] = others + tail)
ordered[weights[others] + tail] = weights[0] + others + tail;
tail = (weights[others] << 1);
for (ascending_stbl(tail, dists[0][1], ordered); tail--; ranks[ordered[tail]] = tail);
for (tail = weights[others]; tail--; ordered[tail] = others + tail)
ordered[weights[others] + tail] = weights[0] + others + tail;
ascending_stbl(weights[others] << 1, dists[0][0], ordered);
memset(sums, 0, (weights[others] << 1) * sizeof(sums[0]));
for (tail = 0; tail < (weights[others] << 1); tail++)
if (ordered[tail] > weights[0]) {
deltas[1][ordered[tail] -= weights[0]] = 0;
for (next = ranks[ordered[tail] + weights[0]]; next != 0xFFFFFFFFU; next = (next & (next + 1)) - 1)
deltas[1][ordered[tail]] += sums[next];
ordered[tail] += weights[0];
} else
for (next = ranks[ordered[tail]]; next < (weights[others] << 1); next |= next + 1)
sums[next]++;
deltas[1][0] = weights[others];
for (tail = others + (tail >> 1); others < tail; others++)
sum += weights[others] * (unsigned long)(
(deltas[0][ancestors[others]] - deltas[0][others])
- (deltas[1][ancestors[others]] - deltas[1][others])
);
}
total += sum >> 1;
others = offsets[history[at] + 1] - offsets[history[at]];
memcpy(&history[at], &forward[offsets[history[at]]], others * sizeof(history[0]));
at += others;
}
printf("%lu", total);
free(dists);
return 0;
}
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
#define FO(i,a,b) for (int i = (a); i < (b); i++)
#define sz(v) int(v.size())
using namespace std;
typedef long long ll;
typedef pair < ll,ll> E;
#define dx first
#define dy second
struct edge {
int o;
ll dx, dy;
edge(int o=0, ll dx=0, ll dy=0) : o(o), dx(dx), dy(dy) {}
};
vector < edge> u[100005];
int n; ll DX, DY;
ll Y[100005], X[100005];
int sc[100005];
void delete_from(int x, int y) {
FO(i,0,sz(u[x])) if (u[x][i].o == y) {
swap(u[x][i],u[x].back());
u[x].pop_back();
return;
}
}
void delete_node(int x) {
FO(i,0,sz(u[x])) {
delete_from(u[x][i].o,x);
}
}
void resetsc(int x, int p) {
sc[x] = 1;
FO(i,0,sz(u[x])) if (u[x][i].o != p) {
resetsc(u[x][i].o,x);
sc[x] += sc[u[x][i].o];
}
}
int find_centre(int x, int p, int tsz) {
int lsz = tsz-sc[x];
FO(i,0,sz(u[x])) if (u[x][i].o != p) {
lsz = max(lsz, sc[u[x][i].o]);
int y = find_centre(u[x][i].o,x,tsz);
if (y != -1) return y;
}
if (2*lsz < = tsz+5) return x;
return -1;
}
void getl(int x, int p, vector < E> &v, ll dx, ll dy) {
if (dx != 0 || dy != 0) v.push_back(E(dx,dy));
FO(i,0,sz(u[x])) if (u[x][i].o != p) {
getl(u[x][i].o, x, v, dx+u[x][i].dx, dy+u[x][i].dy);
}
}
bool cmp(E a, E b) {
if (a.dx != b.dx) return a.dx < b.dx;
else return a.dy < b.dy;
}
ll res;
vector < ll> bit;
void ub(int y, int dv) {
for (;y < sz(bit);y+=y&-y) bit[y] += dv;
}
ll qb(int y) {
ll r = 0;
for (;y>0;y-=y&-y) r += bit[y];
return r;
}
ll doitbf(vector < E> p) {
ll RES = 0;
FO(i,0,sz(p)) FO(j,0,i) if (p[i].dx+p[j].dx <= DX && p[i].dy+p[j].dy <= DY) RES++;
return RES;
}
ll doit(vector < E> p) {
//printf("DOIT\n");
//FO(i,0,sz(p)) printf("%lld,%lld\n", p[i].dx, p[i].dy);
ll RES = 0;
vector < E> q;
vector<ll> y;
FO(i,0,sz(p)) {
if (p[i].dx+p[i].dx < = DX && p[i].dy+p[i].dy <= DY) RES--;
ll qdx = DX-p[i].dx;
ll qdy = DY-p[i].dy;
if (qdx >= 0 && qdy >= 0) q.push_back(E(qdx, qdy));
}
FO(i,0,sz(p)) y.push_back(p[i].dy);
FO(i,0,sz(q)) y.push_back(q[i].dy);
sort(y.begin(),y.end());
y.resize(unique(y.begin(),y.end())-y.begin());
bit.resize(sz(y)+5);
FO(i,0,sz(bit)) bit[i] = 0;
sort(p.begin(),p.end(),cmp);
sort(q.begin(),q.end(),cmp);
int pi = 0, qi = 0;
while (qi < sz(q)) {
if (pi < sz(p) && !cmp(q[qi],p[pi])) {
int yv = lower_bound(y.begin(),y.end(),p[pi].dy)-y.begin()+1;
ub(yv,1);
pi++;
} else {
int yv = lower_bound(y.begin(),y.end(),q[qi].dy)-y.begin()+1;
RES += qb(yv);
qi++;
}
}
RES /= 2;
return RES;
}
void testdoit() {
vector < E> v;
DX = DY = 100;
FO(i,0,1000) v.push_back(E(rand()%DX,rand()%DY));
printf("%lld %lld\n", doit(v), doitbf(v));
}
void solve(int x) {
if (sz(u[x]) == 0) return;
resetsc(x,-1);
x = find_centre(x,-1,sc[x]);
vector < E> cv;
cv.push_back(E(0,0));
FO(i,0,sz(u[x])) {
vector < E> v;
getl(u[x][i].o,x,v,u[x][i].dx,u[x][i].dy);
res -= doit(v);
FO(j,0,sz(v)) cv.push_back(v[j]);
}
res += doit(cv);
delete_node(x);
FO(i,0,sz(u[x])) solve(u[x][i].o);
}
int main() {
//testdoit();
//return 0;
scanf("%d %lld %lld", &n, &DX, &DY);
FO(i,0,n) {
scanf("%lld %lld", &X[i], &Y[i]);
}
FO(i,0,n-1) {
int a,b; scanf("%d %d", &a, &b); a--; b--;
u[a].push_back(edge(b,abs(X[a]-X[b]),abs(Y[a]-Y[b])));
u[b].push_back(edge(a,abs(X[a]-X[b]),abs(Y[a]-Y[b])));
}
solve(0);
ll T = (n * 1ll * (n-1)) / 2;
printf("%lld\n", T - res);
}
#3 Code Example with Java Programming
Code -
Java Programming
import java.io.*;
import java.util.*;
public class Solution {
static class Pair implements Comparable < Pair> {
long fi;
long se;
public Pair(long fi, long se) {
this.fi = fi;
this.se = se;
}
@Override
public int compareTo(Pair o) {
if (fi != o.fi) {
return fi > o.fi ? 1 : -1;
}
if (se == o.se) {
return 0;
}
return se > o.se ? 1 : -1;
}
}
static boolean[] cut;
static int[] size;
static int getSize(int v, int p) {
size[v] = 1;
for (int u: e[v]) {
if (u != p && ! cut[u]) {
size[v] += getSize(u, v);
}
}
return size[v];
}
static Pair[] a;
static List < Integer>[] e;
static Pair[] b;
static int getDist(int v, int p, int i, long hh, long vv) {
hh += Math.abs(a[v].fi - a[p].fi);
vv += Math.abs(a[v].se - a[p].se);
b[i++] = new Pair(hh, vv);
for (int u: e[v]) {
if (u != p && ! cut[u]) {
i = getDist(u, v, i, hh, vv);
}
}
return i;
}
static public int lowerBound(long[] arr, int len, long key) {
if (key < = arr[0]) {
return 0;
}
if (key > arr[len - 1]) {
return 0;
}
int index = Arrays.binarySearch(arr, 0, len, key);
if (index < 0) {
index = - index - 1;
if (index < 0) {
return 0;
}
}
while (index > 0 && arr[index-1] == key) {
index--;
}
return index;
}
static int upperBound(long[] arr, int len, long key) {
int index = Arrays.binarySearch(arr, 0, len, key);
if (index < 0) {
index = - index - 1;
if (index < 0) {
return 0;
}
if (index >= len) {
return len;
}
}
while (index < len && arr[index] == key) {
index++;
}
return index;
}
static int[] fenwick;
static long[] c;
static long h;
static long v;
static long calc(int l, int r) {
int n = r-l;
long ret = 0;
Arrays.sort(b, l, r);
for (int i = l; i < r; i++) {
c[i-l] = b[i].se;
}
Arrays.sort(c, 0, n);
Arrays.fill(fenwick, 0, n, 0);
for (int j = l, i = r; --i >= l; ) {
for (; j < r && b[j].fi+b[i].fi <= h; j++)
for (int x = lowerBound(c, n, b[j].se); x < n; x |= x+1) {
fenwick[x]++;
}
for (int x = upperBound(c, n, v-b[i].se); x > 0; x &= x-1) {
ret += fenwick[x-1];
}
}
return ret;
}
static Object[] divide(int l, int v) {
getSize(v, -1);
int nn = size[v];
int p = -1;
for(;;) {
int ch = -1;
for (int u: e[v]) {
if (u != p && ! cut[u] && 2*size[u] >= nn) {
ch = u;
break;
}
}
if (ch < 0) {
break;
}
p = v;
v = ch;
}
cut[v] = true;
b[l] = new Pair(0, 0);
int i = l+1;
long ret = 0;
for (int u: e[v]) {
if (! cut[u]) {
Object[] r = divide(i, u);
ret += (long)r[1];
getDist(u, v, i, 0, 0);
ret -= calc(i, (int)r[0]);
i = (int)r[0];
}
}
cut[v] = false;
ret += calc(l, i) - 1;
return new Object[]{i, ret};
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
h = Long.parseLong(st.nextToken());
v = Long.parseLong(st.nextToken());
a = new Pair[n];
e = new List[n];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
long fi = Long.parseLong(st.nextToken());
long se = Long.parseLong(st.nextToken());
a[i] = new Pair(fi, se);
e[i] = new LinkedList < >();
}
for (int i = 0; i < n - 1; i++) {
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken()) - 1;
int v = Integer.parseInt(st.nextToken()) - 1;
e[u].add(v);
e[v].add(u);
}
cut = new boolean[n];
size = new int[n];
b = new Pair[n];
fenwick = new int[n];
c = new long[n];
long result = (long)(n-1)*n - ((long)divide(0, 0)[1]) >> 1;
bw.write(String.valueOf(result));
bw.newLine();
bw.close();
br.close();
}
}
#4 Code Example with Python Programming
Code -
Python Programming
from collections import namedtuple
import bisect
import sys
DistTuple = namedtuple('distance', ['h', 'v'])
def insort_right(arr, dist, hv):
x_key = dist.h if hv == 'h' else dist.v
lo = 0
hi = len(arr)
while lo < hi:
mid = (lo + hi) // 2
a_mid = arr[mid].h if hv == 'h' else arr[mid].v
if x_key < a_mid:
hi = mid
else:
lo = mid + 1
arr.insert(lo, dist)
def bisect_right(arr, x_key, hv):
lo = 0
hi = len(arr)
while lo < hi:
mid = (lo + hi) // 2
a_mid = arr[mid].h if hv == 'h' else arr[mid].v
if x_key < a_mid:
hi = mid
else:
lo = mid + 1
return lo
class DistsGroup:
def __init__(self):
self.delta_h = 0
self.delta_v = 0
dist = DistTuple(0, 0)
self.dists_h_sorted = [dist]
self.dists_v_sorted = [dist]
def append_dist(self, h, v, append=True):
self.delta_h += h
self.delta_v += v
dist = DistTuple(-self.delta_h, -self.delta_v)
if append:
insort_right(self.dists_h_sorted, dist, 'h')
insort_right(self.dists_v_sorted, dist, 'v')
index_h = bisect_right(self.dists_h_sorted, H_max - self.delta_h, 'h')
for elem in self.dists_h_sorted[index_h:]:
self.dists_v_sorted.remove(elem)
del (self.dists_h_sorted[index_h:])
index_v = bisect_right(self.dists_v_sorted, V_max - self.delta_v, 'v')
for elem in self.dists_v_sorted[index_v:]:
self.dists_h_sorted.remove(elem)
del (self.dists_v_sorted[index_v:])
if append:
paths_count = max(0, len(self.dists_v_sorted) - 1)
return paths_count
def append_group(self, other_group, h, v):
good_cross_paths = 0
other_group.append_dist(h, v, False)
dists_h1 = self.dists_h_sorted
delta_h1 = self.delta_h
delta_v1 = self.delta_v
dists_h2 = other_group.dists_h_sorted
delta_h2 = other_group.delta_h
delta_v2 = other_group.delta_v
dists_only_v2 = []
dist_h2_index = 0
dist_h2_len = len(dists_h2)
if len(dists_h1) and len(dists_h2) and dists_h1[-1].h + delta_h1 + dists_h2[-1].h + delta_h2 < H_max and self.dists_v_sorted[-1].v + delta_v1 + other_group.dists_v_sorted[-1].v + delta_v2 < V_max:
good_cross_paths += len(dists_h1) * len(dists_h2)
else:
for dist_h1 in reversed(dists_h1):
rest_h = H_max - (dist_h1.h + delta_h1)
rest_v = V_max - (dist_h1.v + delta_v1)
while dist_h2_index < dist_h2_len:
if dists_h2[dist_h2_index].h + delta_h2 <= rest_h:
bisect.insort_right(dists_only_v2, dists_h2[dist_h2_index].v + delta_v2)
dist_h2_index += 1
else:
break
dist_v2_index = bisect.bisect_right(dists_only_v2, rest_v)
good_cross_paths += dist_v2_index
for dist_h2 in dists_h2:
dist_new = DistTuple((dist_h2.h + delta_h2) - delta_h1, (dist_h2.v + delta_v2) - delta_v1)
self.dists_h_sorted.append(dist_new)
self.dists_v_sorted.append(dist_new)
self.dists_h_sorted.sort()
self.dists_v_sorted.sort(key=lambda k: k.v)
return good_cross_paths
good_paths = 0
N, H_max, V_max = map(int, sys.stdin.readline().split())
junctions = {}
for i in range(1, N + 1):
xi, yi = map(int, sys.stdin.readline().rstrip().split())
junctions[i] = {'x': xi, 'y': yi, 'edges': [], 'dists_group': None}
for i in range(1, N):
ui, vi = map(int, sys.stdin.readline().rstrip().split())
dH = abs(junctions[ui]['x'] - junctions[vi]['x'])
dV = abs(junctions[ui]['y'] - junctions[vi]['y'])
junctions[ui]['edges'].append({'junction_id': vi, 'dH': dH, 'dV': dV})
junctions[vi]['edges'].append({'junction_id': ui, 'dH': dH, 'dV': dV})
one_edge_queue = []
for key, value in junctions.items():
edge_count = len(junctions[key]['edges'])
junctions[key]['edge_count'] = edge_count
if edge_count == 1:
one_edge_queue.append(key)
junctions[key]['dists_group'] = DistsGroup()
while len(one_edge_queue) > 1:
junction_id = one_edge_queue[0]
edge_to_next = junctions[junction_id]['edges'][0]
next_junction_id = edge_to_next['junction_id']
if junctions[next_junction_id]['dists_group']:
paths_added = junctions[next_junction_id]['dists_group'].append_group(junctions[junction_id]['dists_group'], edge_to_next['dH'], edge_to_next['dV'])
good_paths += paths_added
else:
dists_group = junctions[junction_id]['dists_group']
paths_added = dists_group.append_dist(edge_to_next['dH'], edge_to_next['dV'])
good_paths += paths_added
junctions[next_junction_id]['dists_group'] = dists_group
for edge in junctions[next_junction_id]['edges']:
if edge['junction_id'] == junction_id:
junctions[next_junction_id]['edges'].remove(edge)
break
if len(junctions[next_junction_id]['edges']) == 1:
one_edge_queue.append(next_junction_id)
one_edge_queue.remove(junction_id)
print(int(N * (N - 1) / 2) - good_paths)