Count the number of unordered pairs in an un-directed graph

Question

Link to the problem can be found here

Problem Statement

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.

Constraints

2 ≤ N ≤ 10^5

0 ≤ H,V ≤ 10^14

0 ≤ xi,yi ≤ 10^9

I have solved this problem with recursion. But on some of the test cases, my code is timing out.

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

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        long H = in.nextLong();
        long V = in.nextLong();
        List<Vertex> vertex = new ArrayList<>();

        for (int i=0; i < N; i++) {
            Vertex vx = new Vertex(in.nextLong(), in.nextLong());
            vertex.add(vx);
        }
        for (int i=0; i < N-1; i++) {
            int fromPath = in.nextInt()-1;
            int toPath = in.nextInt()-1;
            vertex.get(fromPath).neighbours.add(vertex.get(toPath));
            vertex.get(toPath).neighbours.add(vertex.get(fromPath));
        }

        long count = 0;

        for (int i=0; i < N; i++) {
            count += (N - findUnorderedPairs(vertex.get(i), null, 0, 0, H, V));
        }

        System.out.println(count/2);
        int temp = 0;

    }

    private static long findUnorderedPairs(Vertex vertex, Vertex previousVertex, long hor, long vert, long H, long V) {
        if (hor > H || vert > V) {
            return 0;
        }

        long result = 1;

        for (Vertex v : vertex.neighbours) {
                result += (v != previousVertex) ? findUnorderedPairs(v, vertex, hor + Math.abs(vertex.x - v.x), vert + Math.abs(vertex.y - v.y), H, V) : 0;

        }

        return result;
    }

    private static class Vertex {
        private long x;
        private long y;
        public ArrayList<Vertex> neighbours;

        public Vertex(long x, long y) {
            this.x = x;
            this.y = y;
            neighbours = new ArrayList<>();
        }
    }
}

I have also tried with an implementation of Dijkstras, but no luck there either.

Any suggestions as to how to achieve a speedier solution would really be appreciated.

Answer 1

Here is an O(n log^2 n) solution(it is fast enough for this problem: I managed to get accepted using it, but I will not post my code here because I think that it is more useful to understand the algorithm itself rather than to look at its implementation).

1. Let's use a centroid decomposition of a tree. You can read more about it here: http://www.ioi2011.or.th/hsc/tasks/solutions/race.pdf.

2. How to merge solutions for subtrees? We can represent each point as a pair (x, y) where x and y are the distance from this point to the current root by x and y axes. For each point, we want to count the number such other points that x1 + x2 <= H and y1 + y2 <= W, or, put it another way, x1 <= H - x2 and y1 <= W - y2. Thus, all "good" points for a fixed point are located in a (0, 0, H - x, W - y) rectangle. Counting the number of such points is a standard problem and it can be solved in O(n log n) time using a sweep line with a treap(or coordinates compression and a binary index tree).

3. There is one little problem here: we should not count points that come from the same subtree. We can easily fix it by running the same algorithm for each subtree and subtracting the result from the answer.

4. The merge step is done in O(n log n) time. Thus, the total time complexity is O(n log^2 n).

I know that this explanation is not very detailed but it seems to me that it shouldn't be too difficult to come up with a complete solution using the key ideas described here.