计算无向图中无序对的数量

Question

Link可以找到问题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

我已经用递归解决了这个问题。但是在某些测试用例上，我的代码超时了。

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

我也尝试过 Dijkstras 的实现，但也不走运。

任何关于如何实现更快解决方案的建议都将不胜感激。

Answer 1

这是一个 O(n log^2 n) 解决方案（对于这个问题来说它足够快：我设法通过使用它被接受，但我不会 post 我的代码在这里因为我认为它更有助于理解算法本身而不是查看其实现）。

让我们使用树的质心分解。您可以在此处阅读更多相关信息：http://www.ioi2011.or.th/hsc/tasks/solutions/race.pdf。
如何合并子树的解？我们可以将每个点表示为一对 (x, y)，其中 x 和 y 是通过 x 和 y 轴从该点到当前根的距离。对于每个点，我们要计算 x1 + x2 <= H 和 y1 + y2 <= W 等其他点的数量，或者换句话说，x1 <= H - x2 和 y1 <= W - y2。因此，固定点的所有 "good" 个点都位于 (0, 0, H - x, W - y) 矩形中。计算这些点的数量是一个标准问题，可以使用带有 treap（或坐标压缩和二叉索引树）的扫描线在 O(n log n) 时间内解决。
这里有一个小问题：我们不应该计算来自同一子树的点。我们可以通过运行对每个子树使用相同的算法并从答案中减去结果来轻松修复它。
合并步骤在 O(n log n) 时间内完成。因此，总时间复杂度为O(n log^2 n)。

我知道这个解释不是很详细，但在我看来，使用此处描述的关键思想想出一个完整的解决方案应该不会太困难。

计算无向图中无序对的数量

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

java

algorithm

optimization

timeout