37ος ΠΔΠ : Κυνήγι φιλοδωρημάτων (tiphunting) - Λύση

Συγγραφέας: Μάκης Αρσένης

Επεξήγηση Εκφώνησης

Μας δίνεται η περιγραφή ενός οδικού δικτύου μιας πόλης με \(N\) σπίτια που συνδέονται μεταξύ τους με \(N-1\) δρόμους διπλής κατεύθυνσης. Η εκφώνηση μας διαβεβαιώνει ότι η πόλη έχει σχεδιαστεί ώστε να υπάρχει (μοναδικό) μονοπάτι που να συνδέει μεταξύ τους οποιαδήποτε δύο σπίτια. Συμπεραίνουμε λοιπόν ότι το γράφημα που αναπαριστά την πόλη είναι ένα δέντρο, όπου οι κορυφές αντιστοιχούν σε σπίτια και οι ακμές σε δρόμους.

Κάθε σπίτι \(i\) μπορεί να προσφέρει ένα μη-αρνητικό φιλοδώρημα \(t_i\), και κάθε δρόμος \(j\) που συνδέει δύο σπίτια \(u, v\) έχει ένα μη-αρνητικό κόστος διάσχισης που θα συμβολίζουμε με \(w_j\) ή ισοδύναμα με \(w_{u, v}\). Ως διαδρομή ορίζουμε μια πεπερασμένη ακολουθία σπιτιών όπου διαδοχικά σπίτια συνδέονται μεταξύ τους άμεσα από κάποιον δρόμο. Παρατηρήστε ότι ο παραπάνω ορισμός επιτρέπει σε μια διαδρομή να περιλαμβάνει το ίδιο σπίτι περισσότερες από μια φορές.

Το κέρδος μιας διαδρομής ορίζεται ως το άθροισμα των φιλοδωρημάτων των σπιτιών από τις οποίες αποτελείται (κάθε σπίτι μπορεί να συνεισφέρει το φιλοδώρημα του το πολύ μια φορά, ακόμα κι αν η διαδρομή το επισκέπτεται περισσότερες φορές) μείον το συνολικό κόστος διάσχισης των δρόμων της διαδρομής, όπου, σε αντίθεση με το άθροισμα των φιλοδωρημάτων, το κόστος κάθε δρόμου προσμετράται κάθε φορά που η διαδρομή τον διασχίζει.

Το αρχείο εισόδου περιέχει \(Q\) ερωτήματα. Κάθε ερώτημα αποτελείται από δύο σπίτια \(L, R\) και μας ζητάει να υπολογίσουμε το μέγιστο δυνατό κέρδος μιας διαδρομής με αφετηρία το σπίτι \(L\) και προορισμό το σπίτι \(R\).

Υποπρόβλημα 1 (\(w_1 = w_2 = \ldots = w_{N-1} = 0\))

Σε αυτό το υποπρόβλημα το κόστος διάσχισης κάθε δρόμου είναι μηδενικό, επομένως η διαδρομή μας μπορεί να επισκεφτεί όλα τα σπίτια και να μαζέψει όλα τα φιλοδωρήματα, ανεξαρτήτως αφετηρίας και προορισμού. Η απάντηση λοιπόν σε κάθε ερώτημα είναι η ίδια, και ίση με το συνολικό άθροισμα \(S = \sum_{i = 1}^N t_i\) των φιλοδωρημάτων.

Δείτε ολόκληρο τον κώδικα εδώ

Γενικές Παρατηρήσεις

Πριν προχωρήσουμε, ας παρατηρήσουμε κάποιες ιδιότητες της βέλτιστης λύσης που θα μας φανούν χρήσιμες σε όλα τα υποπροβλήματα που ακολουθούν.

Παρατήρηση 1: Στη βέλτιστη λύση δεν θα χρειαστεί ποτέ να διασχίσουμε κάποιο δρόμο πάνω από δύο φορές.

Παρατήρηση 2: Η βέλτιστη λύση θα είναι μια διαδρομή η οποία θα περιλαμβάνει το (μοναδικό) μονοπάτι που συνδέει τα σπίτια \(L\) και \(R\), όπου σε κάθε στάση σε κάποιο σπίτι \(u\), θα έχουμε την ευκαιρία να “ξεφύγουμε” για λίγο από το βασικό του μονοπάτι και να εξερευνήσουμε τα σπίτια που συνδέονται με το \(u\) (άμεσα ή έμμεσα μέσω άλλων δρόμων), να μαζέψουμε όσα περισσότερα φιλοδωρήματα μπορούμε, να επιστρέψουμε πάλι στο \(u\) και να συνεχίσουμε προς τον τελικό μας προορισμό. Έτσι, στο τέλος θα έχουμε διασχίσει τους δρόμους που βρίσκονται στο κεντρικό μονοπάτι μεταξύ \(L\) και \(R\) μόνο μια φορά, και για κάθε άλλο δρόμο θα τον έχουμε διασχίσει είτε καμία είτε δύο φορές.

Παρατήρηση 3: Η απάντηση στο ερώτημα \(L, R\) είναι ίδια με την απάντηση στο ερώτημα \(R, L\) λόγω συμμετρίας (οι δρόμοι είναι διπλής κατεύθυνσης).

Υποπρόβλημα 2 (\(N \le 1.000, Q \le 1.000, L = R\)) — Λύση \(\mathcal{O}(N \cdot Q)\)

Ο περιορισμός \(L = R\) απλουστεύει το πρόβλημα καθώς δεν χρειάζεται να ασχοληθούμε με το μέρος της λύσης που περιλαμβάνει το μονοπάτι που αναφέραμε στην Παρατήρηση 2, παρά μόνο με την επιμέρους εξερεύνηση.

Ας φανταστούμε ότι το σπίτι \(L\) από το οποίο ξεκινάμε είναι η ρίζα του δέντρου που αναπαριστά το οδικό δίκτυο. Κάθε σπίτι \(u\) που συνδέεται άμεσα με το \(L\) ορίζει ένα υποδέντρο το οποίο θα συμβολίζουμε με \(\text{subtree}(u)\). Για κάθε ένα από αυτά τα δέντρα, έχουμε να κάνουμε μια ανεξάρτητη επιλογή:

να διασχίσουμε το δρόμο \(L \rightarrow u\) κόστους \(w\), να μαζέψουμε όσα περισσότερα φιλοδωρήματα μπορούμε από το \(\text{subtree}(u)\) και να επιστρέψουμε πίσω διασχίζοντας το δρόμο \(u \rightarrow L\) για δεύτερη φορά, ή
να μη διασχίσουμε ποτέ το δρόμο που συνδέει το σπίτι \(L\) με το σπίτι \(u\).

Ας ορίσουμε \(\text{best\_subtree\_tour}[u]\) ως το μέγιστό δυνατό κέρδος που μπορούμε να έχουμε αν ξεκινήσουμε από το σπίτι \(u\), κινούμαστε μόνο μέσα στο υποδέντρο που ορίζει το σπίτι \(u\), και τελικά επιστρέψουμε πάλι στο \(u\).

Είναι φανερό ότι θα ακολουθήσουμε την επιλογή 1 όταν αυτή παράγει κέρδος, δηλαδή όταν \(\text{best\_subtree\_tour}[u] - 2\cdot w \ge 0\). Διαφορετικά η επιλογή 2 είναι καλύτερη — ή ισοδύναμη σε περίπτωση μηδενικού κέρδους.

Μπορούμε να υπολογίσουμε όλες τις τιμές \(\text{best\_subtree\_tour}\) εφαρμόζοντας τον παρακάτω αναδρομικό τύπο:

\[\text{best\_subtree\_tour}[u] = t_u + \sum_{v \in \text{children}(u)} \left( \text{best\_subtree\_tour}[v] - 2 \cdot w_{u, v} \right)^+\]

όπου ο συμβολισμός \((x)^+\) σημαίνει \(\max(0, x)\) και \(\text{children}(u)\) είναι το σύνολο με όλα τα παιδιά της κορυφής \(u\).

// Επιστρέφει το κέρδος της βέλτιστης διαδρομής η οποία ξεκινάει
// από την κορυφή `u`, καταλήγει πίσω σε αυτή και παραμένει
// εξ' ολοκλήρου μέσα στο υποδέντρο που ορίζει η `u`. Με άλλα λόγια,
// η διαδρομή απαγορεύεται να διασχίσει το δρόμο `(u, parent)`.
long long best_subtree_tour(long u, long parent) {
  long long sol = tip[u];

  for (auto [v, w]: tree[u]) {
    if (v == parent) continue;
    long long s = best_subtree_tour(v, u);
    sol += positive_part(s - 2*w);
  }

  return sol;
}

Η τελική απάντηση στο ερώτημα βρίσκεται στο \(\text{best\_subtree\_tour}[L]\).

Για τον υπολογισμό όλων των παραπάνω τιμών, χρειάζεται για κάθε κορυφή να υπολογίσουμε ένα άθροισμα που περιλαμβάνει όλα τα παιδιά της, συνεπώς χρειάζεται χρόνος γραμμικός στο πλήθος των κορυφών και των ακμών του δέντρου, άρα \(\mathcal{O}(N)\) για κάθε ερώτημα. Συνολικά η λύση αυτή έχει πολυπλοκότητα \(\mathcal{O}(N \cdot Q)\), η οποία μας καλύπτει για τους περιορισμούς αυτού του υποπροβλήματος.

Ο πλήρης κώδικας βρίσκεται εδώ

Υποπρόβλημα 3 (\(N \le 1.000, Q \le 1.000\)) — Λύση \(\mathcal{O}(N Q)\)

Ας σκεφτούμε τώρα την πιο γενική περίπτωση όπου η διαδρομή μας θα πρέπει να καταλήγει σε κάποιο σπίτι \(R\), πιθανώς διαφορετικό του \(L\). Μπορούμε να ξεκινήσουμε παρόμοια με πριν, θεωρώντας αυτή τη φορά ότι η κορυφή \(R\) είναι η ρίζα του δέντρου. Η αφετηρία \(L\) θα βρίσκεται σε κάποιο μικρότερο υποδέντρο. Ξεκινώντας από την \(L\), είμαστε ελεύθεροι να εξερευνήσουμε το υποδέντρο \(\text{subtree}(L)\) για το οποίο μπορούμε να υπολογίσουμε τη βέλτιστη διαδρομή χρησιμοποιώντας το \(\text{best\_subtree\_tour}[L]\) που ορίσαμε προηγουμένως.

Σε αντίθεση όμως με πριν, μόλις επιστρέψουμε στο \(L\) θα πρέπει να ανέβουμε ένα επίπεδο παραπάνω, ακολουθώντας το μονοπάτι προς τη ρίζα και μαζεύοντας κι άλλα φιλοδωρήματα στην πορεία. Ας ορίσουμε λοιπόν την ποσότητα \(\text{best\_supertree\_root\_walk}[u]\) ως το μέγιστο κέρδος που μπορούμε να έχουμε όταν ξεκινάμε από το σπίτι \(u\) (χωρίς όμως να συλλέγουμε το φιλοδώρημα του \(u\)), καταλήγουμε τελικά στη ρίζα \(R\) του δέντρου, και σε όλη τη διαδρομή απαγορεύεται να επισκεφτούμε οποιοδήποτε σπίτι βρίσκεται στο υποδέντρο \(\text{subtree}(u)\).

Εάν υπολογίσουμε την τιμή της παραπάνω ποσότητας για την κορυφή \(L\), τότε μπορούμε να υπολογίσουμε την απάντηση του ερωτήματος απλά με το άθροισμα:

\[\text{best\_subtree\_tour}[L] + \text{best\_supertree\_root\_walk}[L].\]

Μπορούμε να υπολογίσουμε όλες τις τιμές \(\text{best\_supertree\_root\_walk}[u]\) από “πάνω προς τα κάτω” χρησιμοποιώντας τις τιμές \(\text{best\_subtree\_tour}\) ως εξής: αν η κορυφή \(u\) είναι η ρίζα, τότε εξ ορισμού \(\text{best\_supertree\_root\_walk}[u] = 0\), διαφορετικά,

\[\begin{align*} \text{best\_supertree\_root\_walk}[u] =& \text{best\_supertree\_root\_walk}[\text{parent}(u)] + \text{best\_subtree\_tour}[\text{parent}(u)] \\ &- (\text{best\_subtree\_tour}[u] - 2 \cdot w_{u, \text{parent}(u)})^+ - w_{u, \text{parent}(u)} \end{align*}\]

Όντως, ο παραπάνω τύπος χρησιμοποιεί την τιμή του \(\text{best\_supertree\_root\_walk}\) για τον γονέα \(\text{parent(u)}\) του \(u\), που μπορούμε να θεωρήσουμε ότι έχουμε ήδη υπολογίσει (θυμηθείτε ότι υπολογίζουμε τις τιμές από πάνω προς τα κάτω), η οποία περιλαμβάνει τη βέλτιστη λύση που αφορά τη διαδρομή από \(\text{parent}(u)\) μέχρι τη ρίζα. Το μόνο που μένει είναι να συμπεριλάβουμε το κομμάτι της διαδρομής που εξερευνά τα σπίτια που συνδέονται στο \(u\) και στον γονέα του. Η τιμή για αυτό το κομμάτι της διαδρομής είναι σχεδόν η τιμή \(\text{best\_subtree\_tour}[\text{parent}(u)]\) που είχαμε ορίσει προηγουμένως, με τη διαφορά ότι αυτή η τιμή πιθανώς να περιλαμβάνει το κόστος της ακμής \((u, \text{parent}[u])\) δύο φορές. Πρέπει λοιπόν να διορθώσουμε την τιμή, αφαιρώντας την κατάλληλη ποσότητα, μόνο όμως όταν αυτή έχει θετικό πρόσημο. Τέλος, σε κάθε περίπτωση, συμπεριλαμβάνουμε και το κόστος διάσχισης του δρόμου \((u, \text{parent}[u])\) ακριβώς μία φορά.

Μια αναδρομική υλοποίηση είναι η παρακάτω:

// Πρώτη διάσχιση η οποία υπολογίζει το `best_subtree_tour` για την κορυφή `u`
// κι όλους τους απογόνους της.
//
// best_subtree_tour[u] = κέρδος της βέλτιστης διαδρομής η οποία ξεκινάει και
// καταλήγει πάλι πίσω στο `u`, παραμένοντας στο υποδέντρο που ορίζει η κορυφή
// `u`. Με άλλα λόγια, η διαδρομή απαγορεύεται να διασχίσει τον δρόμο `(u,
// parent)`.
void compute_best_subtree_tour(long u, long parent) {
  best_subtree_tour[u] = tip[u];

  for (auto [v, w]: tree[u]) {
    if (v == parent) continue;
    compute_best_subtree_tour(v, u);
    best_subtree_tour[u] += positive_part(best_subtree_tour[v] - 2*w);
  }
}

// Δεύτερη διάσχιση η οποία υπολογίζει το `best_supertree_root_walk` για την
// κορυφή `u` κι όλους τους απογόνους της, χρησιμοποιώντας τις τιμές
// `best_subtree_tour` που υπολογίσαμε ήδη στην πρώτη διάσχιση.
//
// best_supertree_root_walk[u] = κέρδος της βέλτιστης διαδρομής η οποία ξεκινάει
// από την κορυφή `u`, καταλήγει στη ρίζα τους δέντρου και μένει πάντα ΕΚΤΟΣ του
// υποδέντρου που ορίζει η `u`. Το φιλοδώρημα της κορυφής `u` ΔΕΝ προσμετράται.
void compute_best_supertree_root_walk(long u, long parent, long w) {
  best_supertree_root_walk[u] = 0;

  // Αν η κορυφή `u` ΔΕΝ είναι ρίζα.
  if (parent != u)
    best_supertree_root_walk[u] =
      best_subtree_tour[parent] + best_supertree_root_walk[parent]
      - positive_part(best_subtree_tour[u] - 2*w) - w;

  for (auto [v, w]: tree[u])
    if (v != parent)
      compute_best_supertree_root_walk(v, u, w);
}

Για την επίλυση ενός ερωτήματος λοιπόν χρειάστηκαν δύο διασχίσεις του δέντρου (μια για τον υπολογισμό των \(\text{best\_subtree\_tour}\), και έπειτα μια για τον υπολογισμό των \(\text{best\_supertree\_root\_walk}\)), οι οποίες γίνονται σε \(\mathcal{O}(N)\) χρόνο. Συνολικά \(\mathcal{O}(N \cdot Q)\) πολυπλοκότητα και γι’ αυτό το υποπρόβλημα. Μπορείτε να δείτε ολόκληρο τον κώδικα εδώ.

Υποπρόβλημα 4 (\(L = R\)) — Λύση \(\mathcal{O}(N + Q)\)

Σε αυτό το υποπρόβλημα το μέγεθος του δέντρου και το πλήθος των ερωτημάτων είναι αρκετά μεγαλύτερο από το προηγούμενο και έτσι η λύση που περιγράψαμε νωρίτερα για το υποπρόβλημα 2 δεν επαρκεί. Θα πρέπει να βρούμε κάποιον τρόπο να απαντάμε τα ερωτήματα χωρίς να διαπερνάμε όλο το δέντρο από την αρχή κάθε φορά. Ο λόγος που χρειαζόταν να διασχίσουμε το δέντρο από την αρχή σε κάθε ερώτημα, ήταν ότι έπρεπε να αλλάξουμε ρίζα, κι έτσι οι τιμές που είχαμε για το \(\text{best\_subtree\_tour}\) δεν θα ήταν έγκυρες για το δέντρο του επόμενου ερωτήματος. Παρ’ όλα αυτά, ας προσπαθήσουμε να σκεφτούμε αν μπορούμε με κάποιο τρόπο να τις εκμεταλλευτούμε ώστε να απαντήσουμε μελλοντικά ερωτήματα.

Ας θεωρήσουμε λοιπόν στο εξής ότι η ρίζα του δέντρου είναι πάντα η κορυφή 1, κι ας υπολογίσουμε τις τιμές \(\text{best\_subtree\_tour}\) όπως τις ορίσαμε παραπάνω. Η απάντηση σε ένα ερώτημα στο οποίο \(L = R \ne 1\), είναι σχεδόν ίση με \(\text{best\_subtree\_tour}[L]\), με τη διαφορά ότι αυτή η τιμή δεν περιλαμβάνει διαδρομές που ανεβαίνουν σε υψηλότερα επίπεδα του δέντρου και γυρνάνε πάλι πίσω στην κορυφή \(L\). Αυτό όμως διορθώνεται εύκολα αν προ-υπολογίσουμε για κάθε κορυφή \(u\) αυτή την τιμή, ας την ονομάσουμε \(\text{best\_\textcolor{red}{supertree}\_tour}[u]\), ώστε να την έχουμε διαθέσιμη όταν τη χρειαστούμε για να απαντήσουμε κάποιο ερώτημα.

Μάλιστα, οι τιμές αυτές μοιάζουν πολύ με τις τιμές \(\text{best\_supertree\_root\_walk}\) που ορίσαμε στο προηγούμενο υποπρόβλημα, με τη διαφορά όμως ότι δεν είναι πλέον αναγκαίο να φτάσουμε μέχρι τη ρίζα, αλλά πρέπει να γυρίσουμε πίσω στην κορυφή \(u\), το οποίο σημαίνει ότι πρέπει να μετρήσουμε το κόστος του δρόμου \((u, \text{parent}(u))\) δύο φορές. Ο τύπος που είχαμε προηγούμενως αλλάζει ως εξής:

\[\begin{align*} \text{best\_supertree\_tour}[u] = ( & \text{best\_supertree\_tour}[\text{parent}(u)] + \text{best\_subtree\_tour}[\text{parent}(u)] \\ &- (\text{best\_subtree\_tour}[u] - 2 \cdot w_{u, \text{parent}(u)})^+ - \textcolor{red}{2} \cdot w_{u, \text{parent}(u)} )^+ \end{align*}\]

Ο προ-υπολογισμός των \(\text{best\_subtree\_tour}\) και \(\text{best\_supertree\_tour}\) με ρίζα την κορυφή 1 μπορεί να γίνει με δύο διασχίσεις του δέντρου σε χρόνο \(\mathcal{O}(N)\) πριν ξεκινήσουμε να απαντάμε ερωτήματα, κι έπειτα για κάθε ερώτημα, μπορούμε να υπολογίσουμε την απάντηση σε σταθερό χρόνο με τον τύπο:

\[\text{best\_subtree\_tour}[L] + \text{best\_supertree\_tour}[L].\]

Συνολικά η λύση αυτή έχει χρονική πολυπλοκότητα \(\mathcal{O}(N + Q)\). Μπορείτε να δείτε ολόκληρο τον κώδικα εδώ.

Υποπρόβλημα 5 (\(L_1 = L_2 = \ldots = L_N\)) — Λύση \(\mathcal{O}(N + Q)\)

Σε αυτή την περίπτωση η αφετηρία και ο προορισμός μπορεί να είναι διαφορετικά σπίτια, όμως η εκφώνηση μας εξασφαλίζει ότι οι αφετηρίες όλων των ερωτημάτων θα είναι οι ίδιες. Αυτό μας επιτρέπει να θέσουμε την κοινή κορυφή \(L\) ως ρίζα και να εφαρμόσουμε τη λύση του υποπροβλήματος 3, υπολογίζοντας όμως τις βοηθητικές τιμές \(\text{best\_subtree\_tour}\) και \(\text{best\_supertree\_root\_walk}\) μόνο μια φορά στην αρχή, και απαντώντας μετά το κάθε ερώτημα σε σταθερό χρόνο. Ο πλήρης κώδικας βρίσκεται εδώ.

Σημείωση: Στο υποπρόβλημα 3 θεωρήσαμε ότι η ρίζα ήταν το σπίτι \(R\), όχι το \(L\) όπως εδώ. Η Παρατήρηση 3 όμως μας εξασφαλίζει ότι αυτή η αλλαγή δεν επηρεάζει την απάντηση.

Υποπρόβλημα 6

Ας προσπαθήσουμε να γενικεύσουμε την προηγούμενη λύση στην περίπτωση που η ρίζα του δέντρου με βάση την οποία προ-υπολογίσαμε τις βοηθητικές τιμές δεν είναι ούτε η αφετηρία ούτε ο προορισμός. Θα ξεκινήσουμε περιγράφοντας τη μορφή της βέλτιστης διαδρομής, κι έπειτα θα δούμε πώς να υπολογίσουμε το κέρδος της σε υπο-γραμμικό χρόνο.

Το μονοπάτι που συνδέει τις κορυφές \(L\) και \(R\) θα έχει την εξής μορφή: ξεκινώντας από την \(L\) ανεβαίνουμε (0 ή περισσότερα) επίπεδα μέχρι να φτάσουμε στον Ελάχιστο Κοινό Πρόγονο (Lowest Common Ancestor) των \(L\) και \(R\), τον οποίο θα συμβολίζουμε με \(\text{LCA}(L, R)\), κι έπειτα κινούμαστε προς χαμηλότερα επίπεδα μέχρι να φτάσουμε στην κορυφή \(R\). Από κάθε κόμβο αυτού του μονοπατιού, μπορούμε να εξερευνήσουμε υποδέντρα ώστε να μαζέψουμε φιλοδωρήματα (ακριβώς όπως στον ορισμό του \(\text{best\_subtree\_tour}\)). Επιπλέον, από την κορυφή \(\text{LCA}(L, R)\) έχουμε τη δυνατότητα να ακολουθήσουμε μια κυκλική διαδρομή που επισκέπτεται υψηλότερα επίπεδα του δέντρου (ακριβώς όπως στον ορισμό του \(\text{best\_supertree\_tour}\) παραπάνω).

Για την ώρα, ας υποθέσουμε ότι γνωρίζουμε τον ελάχιστο κοινό πρόγονο \(z = \text{LCA}(L, R)\).

Έχουμε τις παρακάτω περιπτώσεις:

\(z = L\): Η περίπτωση αυτή μοιάζει πολύ με το υποπρόβλημα 5, με τη διαφορά ότι αφετηρία δεν είναι η ρίζα του δέντρου και συνεπώς αν εφαρμόσουμε τον τύπο \(\text{best\_subtree\_tour}[R] + \text{best\_supertree\_root\_walk}[R]\) θα πάρουμε λάθος απάντηση καθώς ο δεύτερος όρος περιέχει το κέρδος της λύσης που ανεβαίνει μέχρι τη ρίζα αντί αυτής που καταλήγει στην κορυφή \(z\). Αυτό όμως διορθώνεται εύκολα αν αφαιρέσουμε το κέρδος που αντιστοιχεί στο κομμάτι της διαδρομής που ξεκινάει από την κορυφή \(z\) και φτάνει στη ρίζα (το έχουμε ήδη υπολογίσει, είναι το \(\text{best\_supertree\_root\_walk}(z)\)) και αντ’ αυτού προσθέσουμε το κέρδος της κυκλικής διαδρομής που ξεκινάει και επιστρέφει στο \(z\), μαζεύοντας φιλοδωρήματα από κόμβους εκτός του \(\text{subtree}(z)\) (κι αυτή η τιμή είναι διαθέσιμη στο \(\text{best\_supertree\_tour}(z)\)). Συνοψίζοντας, η απάντηση σε αυτή την περίπτωση είναι:
\[\begin{align*} &\text{best\_supertree\_root\_walk}(L) + \text{best\_subtree\_tour}(R) \\ &-\text{best\_supertree\_root\_walk}(z) + \text{best\_supertree\_tour}(z) \end{align*}\]
\(z = L\): Αντίστοιχα με την προηγούμενη περίπτωση, η απάντηση είναι:
\[\begin{align*} &\text{best\_supertree\_root\_walk}(R) + \text{best\_subtree\_tour}(L) \\ &-\text{best\_supertree\_root\_walk}(z) + \text{best\_supertree\_tour}(z) \end{align*}\]
\(z \neq L, R\): Αυτή η περίπτωση είναι συνδυασμός των δύο παραπάνω. Πράγματι, αν μας ρώταγαν ξεχωριστά τα ερωτήματα \(L, z\) κι έπειτα \(z, R\), το άθροισμα των απαντήσεων είναι κοντά στην λύση που παρόντος ερωτήματος. Χρειάζεται όμως προσοχή ώστε να μην διπλομετρήσουμε ορισμένες υπο-διαδρομές, για παράδειγμα εκείνες τις κυκλικές διαδρομές που ξεκινάνε και τερματίζουν στην κορυφή \(z\).

Για να διορθώσουμε την απάντηση, θα φανεί χρήσιμο να γνωρίσουμε τις κορυφές \(u, v\) οι οποίες είναι τα παιδιά της \(z\) που οδηγούν προς τις κορυφές \(L\) και \(R\) αντίστοιχα. Ας υποθέσουμε ότι τις γνωρίζουμε – μπορούμε να τις βρούμε κατα τον υπολογισμό της \(z\) όπως αναφέρουμε παρακάτω. Έχοντας τις \(u, v\), υπολογίζουμε την απάντηση του ερωτήματος συνδυάζοντας τις παρακάτω τιμές:
- (a) το κέρδος της βέλτιστης διαδρομή από την κορυφή \(L\) μέχρι την κορυφή \(u\), έπειτα
- (b) από την \(R\) μέχρι την \(v\),
- (c) το κόστος όλων των κυκλικών διαδρομών που ξεκινάνε και καταλήγουν στην \(z\) παραμένοντας στο υποδέντρο της \(z\) χωρίς όμως να επισκέπτονται τα υποδέντρα των \(u, v\) (τα έχουμε ήδη συμπεριλάβει),
- (d) το κόστος της κυκλικής διαδρομής από το \(z\) στον εαυτό του “προς τα πάνω” (αποφεύγοντας δηλαδή το \(\text{subtree}(z)\)), και τέλος
- (e) το κόστος των δρόμων \((u, z)\) και \((v, z)\).
Συμπερασματικά, ο τύπος για τον υπολογισμό της απάντησης του ερωτήματος \(L, R\) για την περίπτωση \(LCA(L, R) \neq L, R\) είναι:
\[\begin{align*} &\underbrace{(\text{best\_supertree\_root\_walk}[L] - \text{best\_supertree\_root\_walk}[u] - \text{best\_subtree\_tour}[L])}_{(a)} \\ +&\underbrace{(\text{best\_supertree\_root\_walk}[R] - \text{best\_supertree\_root\_walk}[v] - \text{best\_subtree\_tour}[R])}_{(b)} \\ +&\underbrace{( \text{best\_subtree\_tour}[z] - (\text{best\_subtree\_tour}[u] - 2\cdot w_{u, z})^+ - (\text{best\_subtree\_tour}[v] - 2\cdot w_{v, z})^+) }_{(c)} \\ +&\underbrace{\text{best\_supertree\_tour}[z]}_{(d)} \\ -&\underbrace{(w_{u, z} + w_{v, z})}_{(e)} \end{align*}\]

Είδαμε λοιπόν πώς να απαντάμε τα ερωτήματα γρήγορα (και μάλιστα σε σταθερό χρόνο), αρκεί να μπορούμε να υπολογίσουμε τον ελάχιστο κοινό πρόγονο μαζί με τις κορυφές \(u, v\) όπως τις ορίσαμε παραπάνω.

Για να το κάνουμε αυτό αποδοτικά, μπορούμε να χρησιμοποιήσουμε μια τεχνική που λέγεται binary lifting και η οποία μας επιτρέπει να υπολογίσουμε τον ελάχιστο κοινό πρόγονο δύο κορυφών σε χρόνο \(\mathcal{O}(\log N)\), έχοντας κάνει κατάλληλη προεργασία σε χρόνο \(\mathcal{O}(N \log N)\) μια φορά στην αρχή. Προτείνουμε να ανατρέξετε εδώ για μια αναλυτική περιγραφή, ή δείτε τα σχόλια στον κώδικα της λύσης εδώ.

Η λύση που περιγράψαμε έχει συνολική πολυπλοκότητα \(\mathcal{O} ( (N + Q) \log N )\) η οποία μας καλύπτει για τους περιορισμούς του προβλήματος.