Virtual Tree

Το Virtual Tree (ή Auxiliary Tree) αν και απλή τεχνική μπορεί πολλές φορές να αποδειχθεί πολύ χρήσιμη, ιδίως στους διαγωνισμούς πληροφορικής. Δεν είναι γενικά πολύ διαδεδομένο στην κοινότητα του competitive programming (εκτός από την Κίνα), αλλά γνωρίζοντάς το κανείς μπορεί να λύσει προβλήματα δέντρων που διαφορετικά θα χρειαζόντουσαν πολύ δυσκολότερες τεχνικές και περισσότερες γραμμές κώδικα. Συχνά συνδυάζεται με αλγορίθμους δυναμικού προγραμματισμού.

• Ορισμός
• Brute Force κατασκευή σε $Ο(Ν)$
• Κατασκευή σε $O(L \log N)$
• Προβλήματα
• Πηγές

Ορισμός

Με απλά λόγια το Virtual Tree ενός υποσυνόλου κόμβων κλειδιά ενός ριζωμένου δέντρου $T$ είναι το δέντρο το οποίο περιλαμβάνει όλους τους κόμβους κλειδιά καθώς και όλους τους κοντινότερους κοινούς προγόνους (Lowest Common Ancestors - LCA) κάθε ζεύγους αυτών. Οι κόμβοι του Virtual Tree συνδέονται μεταξύ τους με ακμές οι οποίες έχουν μήκος όσο το συντομότερο μονοπάτι μεταξύ τους στο αρχικό δέντρο, $T$.

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

Στη συνέχεια θα δούμε πως να κατασκευάσουμε ένα Virtual Tree με $L$ κόμβους κλειδιά από ένα δέντρο με $N$ κόμβους. Αρχικά θα δούμε την Brute Force λύση που το κατασκευάζει σε $O(N)$ και μέσα από αυτήν θα αποδείξουμε ότι συνολικά (μαζί με τους LCA) ένα Virtual Tree έχει $O(L)$ κόμβους. Μετά θα κατασκευάσουμε μία λύση η οποία δουλεύει σε $O(L \log N)$ με κατάλληλο precomputation.

Brute Force κατασκευή σε $Ο(Ν)$

Μία απλή λύση είναι να ξεκινήσουμε από κάθε κόμβο κλειδί και να ακολουθήσουμε το μονοπάτι προς τα πάνω (από τον πατέρα του) μαρκάροντας παράλληλα τους κόμβους σε έναν πίνακα visited. Σταματάμε μόνο όταν φτάσουμε στην ρίζα ή όταν συναντήσουμε έναν κόμβο που είναι ήδη μαρκαρισμένος. Αν σταματήσαμε λόγω κάποιου μαρκαρισμένου κόμβου τότε, αν δεν βρίσκεται ήδη στο virtual tree, τον προσθέτουμε ως LCA δύο κόμβων κλειδιά. Αυτός ο κόμβος θα πρέπει αναγκαστικά να αποτελεί μέρος του εικονικού μας δέντρου γιατί είναι η “διασταύρωση” δύο κόμβων κλειδιά (του τωρινού και αυτού που τον μάρκαρε πρώτη φορά ως visited). Η πολυπλοκότητα αυτού του αλγορίθμου είναι $O(N)$ γιατί θα περάσουμε και θα μαρκάρουμε κάθε κόμβο του δέντρου $T$ το πολύ μία φορά.

Θεώρημα: Ένα Virtual Tree με $L$ κόμβους κλειδιά περιλαμβάνει συνολικά $O(L)$ κόμβους

Απόδειξη: Από την Brute Force κατασκευή φαίνεται ότι κάθε ένας από τους $L$ κόμβους κλειδιά προσθέτει το πολύ έναν επιπλέον κόμβο στο Virtual Tree. Τελικά δηλαδή, το Virtual Tree έχει $O(L)$ κόμβους συνολικά.

Ακολουθεί υλοποίηση σε C++:

bool visited[MAX_N];
bool in_virt[MAX_N];    // πίνακας που δείχνει αν ένας κόμβος ανήκει στο Virtual Tree
int par[MAX_N];         // πίνακας που δηλώνει τον πατέρα του κάθε κόμβου

// To vtx είναι η λίστα των κόμβων του Virtual tree.
// Αρχικά περιέχει μόνο τους κόμβους κλειδιά.
vector<int> buildVT(vector<int> vtx) {
    memset(visited, false, sizeof visited);
    memset(in_virt, false, sizeof in_virt);

    int L = (int)vtx.size();
    for (int i = 0; i < L; i++) {
        in_virt[vtx[i]] = true;
    }
    for (int i = 0; i < L; i++) {
        int u = vtx[i];
        // -1 θα είναι ο πατέρας μόνο της ρίζας
        while (u != -1 && !visited[u]) {
            visited[u] = true;
            u = par[u];
        }
        if (u != -1 && !in_virt[u]) {
            in_virt[u] = true;
            vtx.push_back(u);
        }
    }

    return vtx;
}

Μετά από αυτή την διαδικασία μπορεί κανείς να κατασκευάσει με έναν παρόμοιο τρόπο το ίδιο το Virtual Tree.

Κατασκευή σε $O(L \log N)$

Ο γρήγορος αλγόριθμος αξιοποιεί το DFS-order των κόμβων του αρχικού δέντρου $T$ έτσι ώστε να διατηρεί συνεχώς την “δεξιότερη” αλυσίδα κόμβων του Virtual Tree. Θα λέμε ότι ένας κόμβος $v$ είναι δεξιά του κόμβου $u$ όταν σε κάποιον πρόγονο του $u$ η DFS ακολούθησε πρώτα το μονοπάτι που οδηγεί στον $u$ και μετά αυτό που οδηγεί στον $v$. Παρακάτω φαίνεται μια αναπαράσταση της δεξιάς αλυσίδας του εικονικού δέντρου.

Ο αλγόριθμος κάνει τα εξής:

• Πρώτα ταξινομεί όλους τους κόμβους κλειδιά ως προς το DFS-order τους (ας πούμε ότι το order του u είναι dfn[u]). Οι κόμβοι επεξεργάζονται με αυτή τη σειρά.

• Παράλληλα διατηρεί ένα stack (stk) το οποίο περιέχει με την σειρά τους κόμβους κλειδιά που ανήκουν στην δεξιά αλυσίδα του Virtual Tree, δηλαδή ο τελευταίος κόμβος που μπήκε stack είναι ο κατώτερος αυτή την στιγμή στην αλυσίδα. Αρχικά το stack περιέχει μία dummy ρίζα, που θεωρούμε ότι βρίσκεται πάνω από την κανονική ρίζα του δέντρου, ώστε να διευκολύνει τα επόμενα βήματα του αλγορίθμου (στο τέλος η ρίζα αυτή πρέπει να αφαιρεθεί).

• Για κάθε νέο κόμβο κλειδί u θα υπολογίζουμε τον LCA του με τον κατώτερο κόμβο της αλυσίδας του Virtual Tree. Ας πούμε τον LCA p. Ο p θα πρέπει αναγκαστικά να περιλαμβάνεται στο μονοπάτι από τον κατώτερο κόμβο κλειδί προς την dummy ρίζα. Θα περάσουμε τους κόμβους της αλυσίδας έναν έναν ξεκινώντας από κάτω μέχρι να βρούμε σε ποια περιοχή θα πρέπει να είναι ο p.

• Όσους κόμβους περνάμε θα τους βγάζουμε από το stack γιατί έτσι κι αλλιώς ο u θα βρίσκεται δεξιά τους (σύμφωνα με τον ορισμό που δώσαμε για το “δεξιά”) και θα αποτελέσει το νέο κατώτερο άκρο της αλυσίδας. Καθώς βγάζουμε τους κόμβους από το stack θα πρέπει να ενώνουμε τον κατώτερο με τον δεύτερο κατώτερο με μια ακμή στο πραγματικό Virtual Tree (αυτό το αναλαμβάνει η συνάρτηση addEdge στην υλοποίηση).

• Αν ο p ανήκει ήδη στο Virtual Tree τότε απλά προσθέτουμε τον u στο stack.

• Διαφορετικά αν έχουμε βρει τον κόμβο a που ανήκει στην αλυσίδα και έχει αμέσως από πάνω του είναι ο b ενώ ενδιάμεσα, στο πραγματικό δέντρο, παρεμβάλλεται ο p τότε πρώτα βάζουμε μια ακμή από τον a στον p, αφαιρούμε τον a, μετά προσθέτουμε τον p στο stack και τελικά ξαναγυρίζουμε στη προηγούμενη περίπτωση άρα προσθέτουμε τον u στο stack.

• Τέλος βάζουμε ακμές μεταξύ όλων των διαδοχικών κόμβων που έχουν μείνει στην δεξιότερη αλυσίδα μέσα στο stack.

Στον κώδικα που ακολουθεί αναπαριστούμε το stack με έναν πίνακα για να μας επιτρέπει να βλέπουμε όχι μόνο το τελευταίο στοιχείο που προστέθηκε αλλά και το προτελευταίο.

int stk[MAX_N], dfn[MAX_N];
// lvl[u] = επίπεδο του κόμβου u στο κανονικό δέντρο.
// Κόμβο με μεγαλύτερο επίπεδο βρίσκονται κάτω από
// αυτούς με μικρότερο. Η ρίζα έχει lvl = 0.
int lvl[MAX_N];

bool comp(int a, int b) {
    return dfn[a] < dfn[b];
}

void addEdge(int u, int v) {
    // ...
}

vector<int> buildVT(vector<int> vtx) {
    sort(vtx.begin(), vtx.end(), comp);

    int top = 0;
    // Εδώ χρησιμοποιούμε το 0 ως dummy ρίζα. Αυτό προϋποθέτει ότι το 0 δεν
    // υπάρχει ως κόμβος στο κανονικό δέντρο! Επίσης σιγουρευτείτε ότι ο
    // dummy κόμβος έχει μικρότερο επίπεδο από όλους τους άλλους: lvl[0] = -1
    lvl[0] = -1;
    stk[top++] = 0;

    int L = (int)vtx.size();
    for (int i = 0; i < L; i++) {
        int u = vtx[i];
        // Προσέξτε ότι η συνάρτηση LCA θα πρέπει να λαμβάνει υπόψη της και
        // τον dummy κόμβο.
        int p = LCA(u, stk[top - 1]);
        // Αρχικά βρίσκουμε σε ποιο μέρος της αλυσίδας βρίσκεται ο p.
        // Φροντίζουμε όμως να κρατήσουμε τον κατώτερο κόμβο μέσα στο stack.
        while (top >= 2 && lvl[stk[top - 2]] >= lvl[p]) {
            addEdge(stk[top - 2], stk[top - 1]);
            top--;
        }

        if (stk[top - 1] != p) {
            // Εδώ βρισκόμαστε στην δεύτερη περίπτωση και θεωρούμε ότι
            //a = stk[top - 1] και b = stk[top - 2]
            addEdge(p, stk[top - 1]);
            top--;
            stk[top++] = p;
            vtx.push_back(p);
        }

        stk[top++] = u;
    }

    // Προσέξτε ότι ξεκινάμε από τη θέση 1 και όχι από τη 0, η οποία περιέχει
    // τον dummy κόμβο.
    for (int i = 1; i < top - 1; i++) {
        addEdge(stk[i], stk[i + 1]);
    }

    return vtx;
}

Η ανάλυση της πολυπλοκότητας δεν είναι δύσκολη. Παρατηρούμε ότι κάθε κόμβος εισάγεται και εξάγεται από το stack ακριβώς μία φορά. Έτσι έχουμε $O(L)$ εισαγωγές/εξαγωγές και αν θεωρήσουμε ότι η συνάρτηση του LCA έχει πολυπλοκότητα $O(\log N)$ τότε συνολικά έχουμε $O(L \log N)$.

Μαζί με την sort που έχει $O(L \log L)$ συνολικά προκύπτει ότι η πολυπλοκότητα για να κατασκευάσουμε το Virtual Tree είναι $O(L \log N)$.

Προβλήματα

• [ΠΔΠ Camp 2018 - Καζάρμα]

• Baltic OI 2017 - Railway

• JOI Open Contest 2014 - Factories

Πηγές

• Virtual Tree, Sengxian’s Blog (μέσω google translate)

Σχόλια