Taxicab Driver's Problem

                            Solution in C :

In   C++  :








#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);
}










In   Java :








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();
}
}