Contare il numero di coppie non ordinate in un non-diretta grafico

Question

Link della problema può essere trovato here

Normativa Problemi

Burger città è una città che consiste di N giunzioni speciali e N -1 percorsi . Esiste esattamente un percorso più breve tra ciascuna coppia di giunzioni . La giunzione i si trova in (xi, yi) e la distanza tra due giunzioni i, j è definita dalla geometria di Taxicab.

Tim ha recentemente concesso a un taxi di lavorare come tassista. Il suo veicolo era molto economico, ma ha un difetto molto grande. Può guidare solo unità H orizzontalmente e unità V verticalmente prima di fare rifornimento.

Se un cliente desidera essere portato da i un nodo ad un altro giunzione j, allora questa macchina è solo in grado di guidare il percorso, IFF la somma delle distanze orizzontali e la somma delle distanze verticali questo percorso sono inferiore o uguale a H e V rispettivamente.

Inoltre, esiste un percorso univoco tra due giunzioni.

Ora ha intenzione di restituire il veicolo al venditore. Ma prima vuole sapere, se ne vale la pena. Ecco perché vuole che conosca il numero di coppie non ordinate (i, j) tali che non sia possibile guidare un cliente dallo svincolo i allo svincolo j.

Vincoli

2 ≤ N ≤ 10^5

0 ≤ H, V ≤ 10^14

0 ≤ xi, yi ≤ 10^9

Ho risolto questo problema con la ricorsione. Ma su alcuni dei casi di test, il mio codice sta scadendo.

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

Ho anche provato con un'implementazione di Dijkstras, ma senza fortuna neanche lì.

Qualsiasi suggerimento su come ottenere una soluzione più rapida sarebbe davvero apprezzato.

Answer 1

Ecco una soluzione O(n log^2 n) (è abbastanza veloce per questo problema: sono riuscito ad accettarla, ma non pubblicherò il mio codice qui perché penso che sia più utile capire l'algoritmo stesso piuttosto che guarda alla sua implementazione).

1. Utilizziamo una decomposizione del centroide di un albero. Puoi leggere maggiori informazioni qui: http://www.ioi2011.or.th/hsc/tasks/solutions/race.pdf.

2. Come unire le soluzioni per sottostrutture? Possiamo rappresentare ogni punto come una coppia (x, y) dove x e sono la distanza da questo punto alla radice corrente tramite gli assi x e .Per ogni punto, vogliamo contare il numero di tali altri punti che è x1 + x2 <= H e y1 + y2 <= W o, in altre parole, x1 <= H - x2 e y1 <= W - y2. Pertanto, tutti i punti "buoni" per un punto fisso si trovano in un rettangolo (0, 0, H - x, W - y). Il conteggio del numero di tali punti è un problema standard e può essere risolto nel tempo O(n log n) utilizzando una linea di sweep con un trear (o compressione delle coordinate e un albero dell'indice binario).

3. C'è un piccolo problema qui: non dovremmo contare i punti che provengono dalla stessa sottostruttura. Possiamo facilmente risolverlo eseguendo lo stesso algoritmo per ogni sottostruttura e sottraendo il risultato dalla risposta.

4. Il passo di unione viene eseguito nel tempo O(n log n). Pertanto, la complessità temporale totale è O(n log^2 n).

So che questa spiegazione non è molto dettagliato, ma mi sembra che non dovrebbe essere troppo difficile da trovare una soluzione completa con le idee chiave qui descritte.