Count the number of unordered pairs in an undirected graph

Question

Link to the problem can be found here.

Problem Statement

Burger Town is a city consisting of N special crossings and N-1 tracks. Between each pair there is exactly one short path intersection. The junction i is located at the point (xi, yi), and the distance between the two transitions i, j is determined by the geometry of the Taxicab.

Tim recently provided a taxi to work as a taxi driver. His car was very cheap, but it has a very big drawback. It can only control H units horizontally and V units vertically before refueling.

If the client wants to be brought from junction I to another j junction, then this car can only go along the route if the sum of the horizontal distances and the sum of the vertical distances to this path are less than or equal to H and V, respectively.

In addition, there is a unique path between any two transitions.

Now he has thoughts on returning the car back to the seller. But first, he wants to know, even if it's worth it. That's why he wants to know the number of unordered pairs (i, j), so that it is not possible to control the client from connection i to transition j.

Limitations

2 ≤ N ≤ 10 ^ 5

0 ≤ H, V ≤ 10 ^ 14

0 ≤ xi, yi ≤ 10 ^ 9

I solved this problem with recursion. But in some test cases, my code is disabled.

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 - vx), vert + Math.abs(vertex.y - vy), 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 also tried with the implementation of Dijkstras, but no luck there either.

Any suggestions on how to reach a faster solution would really be appreciated.

Answer 1

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

• You can use the centroid decomposition of the tree. You can learn more about this here: http://www.ioi2011.or.th/hsc/tasks/solutions/race.pdf .

• How to combine 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 using the x and y axes. For each point we want to calculate the number of other points such that x1 + x2 <= H and y1 + y2 <= W , or, in another way, x1 <= H - x2 and y1 <= W - y2 . Thus, all the “good” points for the fixed point are located in the rectangle (0, 0, H - x, W - y) . Counting the number of such points is a standard problem, and it can be solved O(n log n) times using a sweep line with treap (or compression coordinates and a binary index tree).

• There is one small problem here: we do not have to count the points that come from the same subtree. We can easily fix this by running the same algorithm for each subtree and subtracting the result from the response.

• The merge step is performed 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 should not be too difficult to come up with a complete solution using the basic ideas described here.