34ος ΠΔΠ Καμπ (κοινά)
PRETTYTREE (prettytree)

Έστω ένα ριζωμένο δέντρο $T$ (rooted tree), όχι απαραίτητα δυαδικό. Συμβολίζουμε ως $\mathrm{root}(T)$ τη ρίζα του και ως $\mathrm{size}(T)$ τον αριθμό των κόμβων του. Θα λέμε ότι το $T$ είναι όμορφο αν:

αποτελείται από έναν μοναδικό κόμβο, ή
μπορεί να προκύψει ξεκινώντας από δύο άλλα όμορφα δέντρα $T_1$, $T_2$ με $\mathrm{size}(T_1) \geq \mathrm{size}(T_2)$ και προσθέτοντας μία ακμή ώστε ο κόμβος $\mathrm{root}(T_1)$ να γίνει πατέρας του κόμβου $\mathrm{root}(T_2)$.

Συνεπώς ένα όμορφο δέντρο μεγέθους $N$ μπορεί να κατασκευαστεί με τον εξής τρόπο. Ξεκινάμε έχοντας $N$ μεμονομένους κόμβους, που εξ ορισμού είναι όμορφα δέντρα. Επαναλαμβάνουμε το παρακάτω βήμα $N-1$ φορές: επιλέγουμε δύο διαφορετικά όμορφα δέντρα $T_1$, $T_2$ από αυτά που έχουμε, τέτοια ώστε $\mathrm{size}(T_1) \geq \mathrm{size}(T_2)$, προσθέτουμε μία ακμή ώστε ο κόμβος $\mathrm{root}(T_1)$ να γίνει πατέρας του κόμβου $\mathrm{root}(T_2)$, και έτσι φτιάχνουμε ένα νέο όμορφο δέντρο.

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

Δεδομένα εισόδου (prettytree.in)

Στην πρώτη γραμμή της εισόδου θα υπάρχουν δύο θετικοί ακέραιοι $T$ και $V$: το πλήθος των ερωτημάτων σε αυτό το αρχείο και η εκδοχή του προβλήματος ($V = 1$ για την πρώτη εκδοχή και $V = 2$ για την δεύτερη). Ακολουθούν $T$ ερωτήματα, καθένα από τα οποία έχει την εξής μορφή.

Η πρώτη γραμμή του ερωτήματος περιέχει έναν θετικό ακέραιο αριθμό $N$: το πλήθος κόμβων του δέντρου.
Οι επόμενες $N - 1$ γραμμές περιγράφουν τις ακμές του δέντρου: κάθε γραμμή περιέχει δύο θετικούς ακεραίους $u$ και $p$, όπου υποδηλώνουν ότι ο κόμβος $u$ έχει πατέρα τον κόμβο $p$.

Θεωρούμε ότι οι κόμβοι του δέντρου είναι αριθμημένοι από $1$ μέχρι και $N$.

Δεδομένα εξόδου (prettytree.out)

Η έξοδος θα πρέπει να περιέχει $T$ γραμμές, μία για κάθε ερώτημα. Κάθε γραμμή θα περιέχει την απάντηση στην αντίστοιχη εκδοχή του προβλήματος. Στην πρώτη εκδοχή ($V = 1$) η απάντηση πρέπει να είναι $1$, αν το δέντρο του αντίστοιχου ερωτήματος είναι όμορφο, διαφορετικά $0$. Στην δεύτερη εκδοχή ($V = 2$) η απάντηση πρέπει να είναι ο αριθμός των διαφορετικών τρόπων με τους οποίους μπορεί να κατασκευαστεί το δέντρο του αντίστοιχου ερωτήματος. Επειδή ο αριθμός μπορεί να είναι πολύ μεγάλος, ζητείται να βρείτε το υπόλοιπο (modulo) της διαίρεσης με το $10^9 + 7$.

Παραδείγματα αρχείων εισόδου-εξόδου:

1^o

prettytree.in	prettytree.out
2 1 5 2 1 3 1 4 3 5 3 2 1 2	0 1

Εξήγηση παραδείγματος: Στο πρώτο παράδειγμα είναι $T = 2$, $V = 1$, άρα έχουμε την πρώτη εκδοχή του προβλήματος και πρέπει να αποφανθούμε αν τα δύο δέντρα που δίνονται είναι ή όχι όμορφα. Το πρώτο δέντρο μπορεί να κατασκευαστεί με την παραπάνω διαδικασία, άρα δεν είναι όμορφο. Αντίθετα, το δεύτερο δέντρο είναι όμορφο — κατασκευάζεται απλά κάνοντας τον κόμβο $2$ πατέρα του κόμβου $1$.

2^o

prettytree.in	prettytree.out
3 2 4 2 1 3 1 4 3 2 1 2 5 2 1 3 1 4 3 5 3	2 1 0

Εξήγηση παραδείγματος: Στο δεύτερο παράδειγμα είναι $T = 3$, $V = 2$, άρα έχουμε την δεύτερη εκδοχή του προβλήματος και πρέπει να βρούμε με πόσους διαφορετικούς τρόπους μπορούν τα δέντρα που δίνονται να προκύψουν. Το πρώτο δέντρο που δίνεται είναι όμορφο και μπορεί να κατασκευαστεί με δύο διαφορετικούς τρόπους, αν προσθέσουμε τις ακμές του με τις εξής σειρές:

$4$-$3$, $2$-$1$, $3$-$1$
$2$-$1$, $4$-$3$, $3$-$1$ Το δεύτερο δέντρο του δεύτερου παραδείγματος μπορεί να προκύψει με ένα μόνο τρόπο, ενώ το τρίτο δέντρο δεν είναι όμορφο και δεν μπορεί να προκύψει με κανέναν τρόπο.

Περιορισμοί

$1 \leq T \leq 5$,
$1 \leq V \leq 2$,
$1 \leq N \leq 100.000$.

Subtasks

Για περιπτώσεις ελέγχου συνολικής αξίας 10%, θα είναι $V = 1$ και $1 \leq N \leq 11$.
Για περιπτώσεις ελέγχου συνολικής αξίας 20%, θα είναι $V = 1$ και $1 \leq N \leq 21$.
Για περιπτώσεις ελέγχου συνολικής αξίας 35%, θα είναι $V = 1$ και $1 \leq N \leq 100.000$.
Για περιπτώσεις ελέγχου συνολικής αξίας 15%, θα είναι $V = 2$ και $1 \leq N \leq 11$. Κάθε κόμβος οποιουδήποτε δέντρου θα έχει το πολύ $9$ παιδιά.
Για περιπτώσεις ελέγχου συνολικής αξίας 30%, θα είναι $V = 2$ και $1 \leq N \leq 21$. Κάθε κόμβος οπιουδήποτε δέντρου θα έχει το πολύ $9$ παιδιά.
Για περιπτώσεις ελέγχου συνολικής αξίας 45%, θα είναι $V = 2$ και $1 \leq N \leq 100$. Κάθε κόμβος οπιουδήποτε δέντρου θα έχει το πολύ $9$ παιδιά.
Για περιπτώσεις ελέγχου συνολικής αξίας 65%, θα είναι $V = 2$ και $1 \leq N \leq 200$. Κάθε κόμβος οπιουδήποτε δέντρου θα έχει το πολύ $17$ παιδιά.