Αρχική > 34ος ΠΔΠ > filiki (εκφώνηση)

34ος ΠΔΠ Γ' Φάση: Φιλική Εταιρεία (filiki) - Λύση

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

Μας δίνεται ένα δέντρο (ριζωμένο στον κόμβο \(1\)) και ένας ακέραιος αριθμός \(K\). Μας ζητείται να μαρκάρουμε \(K\) κόμβους του δέντρου, έτσι ώστε η μέγιστη απόσταση ενός κόμβου προς τον κοντινότερο μαρκαρισμένο πρόγονό του να ελαχιστοποιείται.

Παρακάτω θα δούμε \(4\) λύσεις:

  1. Brute Force - Πολύ αργή, πιάνει \(10\%\) των πόντων.
  2. Δυναμικός προγραμματισμός - Δουλεύει μόνο για δυαδικά δέντρα, \(30\%\).
  3. Δυναμικός προγραμματισμός - Επέκταση του προηγούμενου για κάθε δέντρο, \(50\%\).
  4. Δυαδική αναζήτηση - Πιάνει το \(100\%\) των πόντων και δεν στηρίζεται καθόλου στις προηγούμενες λύσεις.

Έτσι, αν σας τρομάζει ο δυναμικός προγραμματισμός, μπορείτε να διαβάσετε απευθείας την πλήρη λύση με δυαδική αναζήτηση. Παρόλα αυτά, θεωρούμε ότι είναι καλό πρόβλημα για να εξασκηθείτε στον δυναμικό πρόγραμματισμο σε δέντρα, παρότι η λύση με δυναμικό προγραμματισμό δεν είναι βέλτιστη.

Λύση \(\mathcal{O}(\binom{N}{K} N)\)

Η πρώτη λύση που θα δούμε είναι μία πολύ αργή brute force. Μαντεύει κάθε πιθανό τρόπο να μαρκάρει \(K\) κόμβους, και υπολογίζει κάθε φορά σε \(\mathcal{O}(N)\) χρόνο το κόστος.

Στα μαθηματικά, με \(\binom{N}{K}\) συμβολίζουμε το πλήθος διαφορετικών τρόπων να μαρκάρουμε \(K\) κόμβους από τους \(N\) συνολικά. Διαβάζεται “\(N\) ανά \(K\)”, ή “\(N\) choose \(K\)” στα αγγλικά. Από εκεί προκύπτει και η πολυπλοκότητα του αλγορίθμου μας.

Αν συμβολίσουμε με \(N!\) το γινόμενο \(1\cdot 2\cdot 3 \cdot \ldots \cdot (N-1) \cdot N\) (διαβάζεται “νι παραγοντικό”), τότε ισχύει

\[\binom{N}{K} = \frac{N!}{K! \cdot (N-K)!}\]

Αυτή η λύση τρέχει για \(N\le 25\) (\(10\%\) των αρχείων ελέγχου), αφού το χειρότερο πιθανό \(K\) είναι το \(12\) και το \(13\) (γενικότερα μεγιστοποιείται πάντα όταν το \(K\) είναι το μισό του \(N\)), και έτσι έχουμε \(\binom{N}{K} N = \binom{25}{12} 25 = 5.200.300 \cdot 25 = 130.007.500\), που είναι διαχειρίσιμο για έναν υπολογιστή μέσα σε ένα δευτερόλεπτο.

Ένας πιθανός κώδικας για να υλοποιήσετε αυτή τη λύση είναι ο εξής:

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

vector<long> d;
vector<vector<long>> e;
long mark[30];

long Solve(long u, long ancestor) {
  long ans = mark[u] ? 0 : d[u] - d[ancestor];
  for (auto neigh : e[u])
    ans = max(ans, Solve(neigh, mark[u] ? u : ancestor));  
  return ans;  
}

int main() {
  FILE *fi = fopen("filiki.in", "r");
  FILE *fo = fopen("filiki.out", "w");  
  long N, K, par, weight, ans=0;

  fscanf(fi, "%ld %ld", &N, &K);
  d.resize(N + 1);
  e.resize(N + 1);
  d[1] = 0;
  for (long i = 2; i <= N; ++i) {
    fscanf(fi, "%ld %ld", &par, &weight);
    e[par].push_back(i);
    d[i] = d[par] + weight;
    ans += weight; //upper bounding ans
  }

  mark[1] = 1;
  //this code generates all ways to mark K-1 elements
  for(long i=1; i<K; ++i) mark[N-i+1] = 1;
  do {
    ans = min(ans, Solve(1,1));
  } while(next_permutation(mark+2, mark+N+1));

  fprintf(fo, "%ld\n", ans);
  fclose(fi), fclose(fo);
}

Λύση \(\mathcal{O}(N^2K^2)\) για δυαδικά δέντρα

Αυτή η λύση στηρίζεται στον δυναμικό προγραμματισμό (δείτε εδώ). Παρουσιάζουμε μία πρώτη σκέψη που μπορεί να κάνει κανείς, η οποία όμως έχει ένα πρόβλημα. Φανταστείτε ότι μας δίνεται ένας κόμβος \(u\) και ένας αριθμός \(k\le K\), και μας ζητείται να λύσουμε το εξής υποπρόβλημα: Αντί για το αρχικό δέντρο, έχουμε μόνο το υπόδεντρο του \(u\), κι αντί για δυνατότητα \(K\) μαρκαρισμάτων, μπορούμε να μαρκάρουμε μόνο \(k\) κόμβους. Προσέξτε τη διαφορά μεταξύ μικρού \(k\) και κεφαλαίου \(K\), ισχύει ότι \(k \le K\). Για παράδειγμα αν το αρχικό δέντρο είναι αυτό στα αριστερά, τότε το υποπρόβλημα που ορίζεται από τα \(u=3, k=2\) θα ήταν αυτό στα δεξιά:

Αυτή είναι μια κλασική προσέγγιση δυναμικού προγραμματισμού σε δέντρα. Δυστυχώς εν προκειμένω δεν φαίνεται να λειτουργεί αποδοτικά. Η μόνη αναδρομή που μπορούμε να σκεφτούμε θα λειτουργούσε κάπως έτσι: πρώτα θα μάντευε όλους τους απογόνους του \(u\) οι οποίοι στην βέλτιστη λύση είναι μαρκαρισμένοι και για τους οποίους ο κοντινότερος μαρκαρισμένος τους πρόγονος είναι ο ίδιος ο \(u\) (δηλαδή τίποτα ανάμεσά τους δεν είναι μαρκαρισμένο). Κατόπιν θα μάντευε πόσοι κόμβοι θα μαρκαριστούν στο υπόδεντρο του καθενός από αυτούς τους κόμβους, και μετά θα έκανε αναδρομή στο υπόδεντρό τους. Όμως οι μαντεψιές αυτές είναι πολύ ακριβές, και δεν εκμεταλλεύονται καθόλου τη δυαδική φύση του δέντρου. Έτσι, μια τέτοια προσέγγιση θα ήταν πολύ αργή.

Ιδανικά θα θέλαμε η αναδρομή μας να εξαρτάται μόνο από τα \(2\) παιδιά του κόμβου \(u\), έτσι ώστε να χρειάζονται πολύ λιγότερες μαντεψιές. Το πρόβλημα είναι ότι αν μαρκάρω τον \(u\) και μετά κάνω αναδρομή σε ένα παιδί του \(v\), πιθανώς να μη θέλω να μαρκάρω τον \(v\). Αν όμως μετά (πάλι λόγω αναδρομής) πάω σε ένα παιδί \(w\) (εγγόνι του \(u\)), τότε ο \(w\) δεν θα ξέρει πώς να χρεωθεί, γιατί χρειάζεται να μάθει πρώτα τον κοντινότερο μαρκαρισμένο πρόγονό του. Στο παράδειγμα που αναφέρουμε θα έπρεπε να γνωρίζει ότι ο πρόγονος αυτός είναι ο \(u\). Για τον λόγο αυτό, τροποποιούμε τον δυναμικό προγραμματισμό μας ώστε να γνωρίζουμε και τον κοντινότερο πρόγονο του \(u\) ο οποίος είναι μαρκαρισμένος.

Ανακεφαλαιώνοντας, ο δυναμικός μας προγραμματισμός θα λειτουργεί ως εξής. Δεδομένου ενός κόμβου \(u\), ενός προγόνου \(y\) του \(u\) και ενός αριθμού \(k\le K\), πρέπει να λύσουμε το πρόβλημα στο υπόδεντρο του \(u\), μαρκάροντας το πολύ \(k\) κόμβους, και με δεδομένο ότι ο κοντινότερος πρόγονος του \(u\) που είναι μαρκαρισμένος είναι ο \(y\). Για παράδειγμα, αν το αρχικό δέντρο είναι αυτό στα αριστερά, τότε το υποπρόβλημα που ορίζεται από τα \(u=3, y=1, k=2\) είναι το εξής:

Για συντομία, θα περιγράφουμε ένα υποπρόβλημα ως \([u,y,k]\). Θέλουμε την λύση του \([1,1,K]\), την οποία θα υπολογίσουμε αναδρομικά. Θα γράφουμε επίσης \(L(u), R(u)\) για να αναφερθούμε στο αριστερό και το δεξί παιδί του \(u\).

Πώς λύνουμε λοιπόν το \([u,y,k]\); Απλά πρέπει να σκεφτούμε πολλές περιπτώσεις:

  • Αν μαρκάρω τον \(u\), τότε πληρώνω όσο η απόσταση του \(u\) απ’ τον \(y\), και λύνω αναδρομικά τα \(2\) υπόδεντρα. Επειδή δεν ξέρω όμως πόσους κόμβους να μαρκάρω σε κάθε υπόδεντρο, πρέπει να το μαντέψω. Δοκιμάζω λοιπόν να δώσω \(k'\) κόμβους στο αριστερό υπόδεντρο, και τους υπόλοιπους \(k-k'-1\) στο δεξί υπόδεντρο. Δοκιμάζω προφανώς όλες τις τιμές \(k'\le k-1\). Αρκεί λοιπόν για όλες αυτές τις δοκιμές να λύσω τα \([L(u), u, k']\) και \([R(u), u, k-k'-1]\).
  • Αν δεν μαρκάρω τον \(u\) τότε πρέπει να κάνω τις ίδιες μαντεψιές για τα \(2\) υπόδεντρα, αλλά αυτή τη φορά \(k'\le k\) και το δεξί υπόδεντρο θα πάρει \(k-k'\) πιθανά μαρκαρίσματα (επειδή ο \(u\) έμεινε αμαρκάριστος). Επιπλέον, ο κοντινότερος πρόγονος που είναι μαρκαρισμένος παραμένει ο \(y\), όχι ο \(u\). Άρα καλούμαστε να λύσουμε τα \([L(u), y, k']\) και \([R(u), y, k-k']\).

Ο τρόπος με τον οποίο συνδυάζουμε τις λύσεις είναι αρκετά προφανής για όποιον έχει μια μικρή εξοικείωση με δυναμικό προγραμματισμό, και θεωρούμε ότι φαίνεται καλύτερα στον παρακάτω κώδικα. Η πολυπλοκότητα είναι \(\mathcal{O}(N^2K^2)\), επειδή έχουμε \(\mathcal{O}(N^2K)\) διαφορετικά υποπροβλήματα, και για το καθένα χρειαζόμαστε χρόνο \(\mathcal{O}(K)\) για να δοκιμάσουμε όλα τα \(k'\).

#include <cstdio>
#include <vector>
#include <algorithm>

#define INF 0x3f3f3f3f
#define MAXN 150
#define MAXK 150

using namespace std;

vector<long> e[MAXN+1];
long d[MAXN+1], dp[MAXN+1][MAXN+1][MAXK+1];
bool computed[MAXN+1][MAXN+1][MAXK+1];

long Solve(long u, long y, long k) {
  if (computed[u][y][k]) return dp[u][y][k];
  computed[u][y][k] = true;
  
  if (e[u].size()==0) dp[u][y][k] = k==0 ? d[u]-d[y] : 0;
  else {
    dp[u][y][k] = INF;
    //If we mark u
    if (k>0)
      for(long kt=0; kt < k; ++kt)
	dp[u][y][k] = min(dp[u][y][k], max(Solve(e[u][0], u, kt),
					   (e[u].size()>1 ? Solve(e[u][1], u, k-kt-1) : 0)));
    //If we don't mark u
    for(long kt=0; kt <= k; ++kt)
      dp[u][y][k] = min(dp[u][y][k], max(max(d[u]-d[y], Solve(e[u][0], y, kt)),
					 (e[u].size()>1 ? Solve(e[u][1], y, k-kt) : 0)));    
  }
  return dp[u][y][k];
}

int main() {
  FILE *fi = fopen("filiki.in", "r");
  FILE *fo = fopen("filiki.out", "w");  
  long N, K, par, weight;

  fscanf(fi, "%ld %ld", &N, &K);
  d[1] = 0, d[0] = -INF; //to force 1 to be marked
  for (long i = 2; i <= N; ++i) {
    fscanf(fi, "%ld %ld", &par, &weight);
    e[par].push_back(i);
    d[i] = d[par] + weight;
  }

  fprintf(fo, "%ld\n", Solve(1,0,K));
  fclose(fi), fclose(fo);
}

Λύση \(\mathcal{O}(N^2K^2)\) για γενικά δέντρα

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

Ας εξετάσουμε την παρακάτω εικόνα.

Τι ακριβώς έχουμε κάνει; Πολύ απλά, όποτε ο \(u\) έχει παραπάνω από δύο παιδία, κρατάει μόνο ένα από αυτά ως το αριστερό του παιδί, και δημιουργεί ένα ψεύτικο νέο παιδί ως το δεξί του παιδί. Ο ψευδοκόμβος αυτός είναι υπεύθυνος για τα υπόλοιπα παιδιά του \(u\), τα οποία τα δημιουργούμε ακριβώς με τον ίδιο τρόπο. Μια αναπαράσταση αυτή της διαδικασίας φαίνεται εδώ:

Έτσι ο κώδικάς μας παραμένει ίδιος, με την διαφορά ότι μετασχηματίζουμε το δέντρο σε δυαδικό, όπως φαίνεται εδώ:

void Convert(long uOld, long neibIndex, long uNew) {
  //if at most 2 neighbors left, append them and recurse
  if(eOld[uOld].size() - neibIndex <= 2) {
    for(long i=neibIndex; i<eOld[uOld].size(); ++i) {
      e[uNew].push_back(eOld[uOld][i]);
      Convert(eOld[uOld][i], 0, eOld[uOld][i]);
    }
    return;
  }

  //else, append the first node and recurse
  e[uNew].push_back(eOld[uOld][neibIndex]);
  Convert(eOld[uOld][neibIndex], 0, eOld[uOld][neibIndex]);

  //and then create a fake node to recurse
  e[uNew].push_back(++currNode);
  d[currNode] = d[uOld];
  Convert(uOld, neibIndex+1, currNode);
}

Επιπλέον προσθέτουμε τις εξής γραμμές μέσα στην main συνάρτηση:

  currNode = N;
  Convert(1,0,1);

και θυμόμαστε να διπλασιάσουμε το μέγεθος των πινάκων, επειδή το πλήθος κόμβων το πολύ να διπλασιαστεί.

Ο μετασχηματισμός γίνεται σε γραμμικό χρόνο. Επομένως η πολυπλοκότητα παραμένει \(\mathcal{O}(N^2K^2)\).

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

Λύση \(\mathcal{O}(N\log{(\mathrm{MAX\_COST})})\) για γενικά δέντρα

Η λύση αυτή ακολουθεί μια πολύ διαφορετική προσέγγιση. Είναι πολύ γενική και αξίζει να την έχετε πάντα στο μυαλό σας. Εν προκειμένω μας δίνεται το μέγιστο πλήθος μαρκαρισμάτων \(K\), και προσπαθούμε να βελτιστοποιήσουμε το κόστος. Αξίζει πάντα να σκεφτόμαστε και το αντίστροφο πρόβλημα: τι θα κάναμε αν μας δίνανε ένα αποδεκτό κόστος \(C\), και μας ζητούσανε να το πετύχουμε μαρκάροντας το ελάχιστο πλήθος κόμβων;

Γιατί αξίζει να σκεφτούμε αυτό το αντίστροφο πρόβλημα; Επειδή μπορούμε να λύσουμε το αρχικό μας πρόβλημα ως εξής: Υποθέτουμε ότι το βέλτιστο κόστος είναι \(0\), και λύνουμε το αντίστροφο πρόβλημα. Αν το πλήθος κόμβων που χρειάζεται να μαρκάρουμε για να πετύχουμε κόστος \(0\) είναι το πολύ \(K\), τότε πράγματι το βέλτιστο κόστος είναι \(0\). Αλλιώς, δοκιμάζουμε ξανά, αλλά αυτή τη φορά υποθέτουμε ότι το βέλτιστο κόστος είναι \(1\). Συνεχίζουμε με αυτό τον τρόπο μέχρι να βρούμε τη σωστή απάντηση. Προσέξτε ότι αυτό μοιάζει με σειριακή αναζήτηση του βέλτιστου κόστους.

Παρατηρούμε όμως ότι οι δύο αυτές ποσότητες σχετίζονται άμεσα. Όσο περισσότερα μαρκαρίσματα έχουμε, τόσο μικρότερο κόστος μπορούμε να πετύχουμε. Κι απ’ την ανάποδη, όσο μεγαλύτερο είναι το αποδεκτό κόστος που μπορούμε να πληρώσουμε, τόσο λιγότερους κόμβους χρειάζεται να μαρκάρουμε. Επομένως αντί για σειριακή αναζήτηση, μπορούμε να κάνουμε δυαδική αναζήτηση. Και πάλι μαντεύουμε το βέλτιστο κόστος, και κοιτάμε αν έχουμε αρκετά μαρκαρίσματα ώστε να το πετύχουμε. Οι δοκιμές που κάνουμε όμως τώρα υπαγορεύονται από μία δυαδική αναζήτηση, αντί για μία σειριακή. Ο παρακάτω κώδικας κάνει ακριβώς αυτή τη δυαδική αναζήτηση, υποθέτωντας ότι ήδη ξέρουμε να λύνουμε το αντίστροφο πρόβλημα.

  while (lo < hi) {
    mid = (lo + hi) / 2;
    if (MinK(1, mid) + 1 <= K) hi = mid;
    else lo = mid + 1;
  }

  fprintf(fo, "%ld\n", lo);

Σημείωση: Για τεχνικούς λόγους, βολεύει ο κώδικάς της συνάρτησης \(\texttt{MinK}\) να μην μαρκάρει την ίδια τη ρίζα, για αυτό και προσθέτουμε \(1\) μόνοι μας όταν κάνουμε τη δυαδική αναζήτηση.

Βλέπουμε λοιπόν ότι αρκεί να λύσουμε το εξής πρόβλημα: Αν μας δίνεται ένα αποδεκτό κόστος \(C\), ποιο είναι το ελάχιστο πλήθος κόμβων που χρειάζεται να μαρκάρουμε; Το καλό είναι ότι αυτό το πρόβλημα μπορεί να λυθεί με έναν άπληστο αλγόριθμο, σε γραμμικό χρόνο. Πώς;

Ας υποθέσουμε για μια στιγμή ότι το δέντρο μας έχει βάθος το πολύ \(C\), δηλαδή ότι η μέγιστη απόσταση από τη ρίζα ως τα φύλλα είναι το πολύ \(C\). Σε αυτή την περίπτωση θα αρκούσε να μαρκάρουμε τη ρίζα. Τι συμβαίνει τώρα όταν έχουμε ένα κόμβο \(u\) τέτοιο ώστε το υπόδεντρό του να έχει βάθος το πολύ \(C\); Φαίνεται ότι θέλουμε να μαρκάρουμε τον \(u\) ώστε να καλύψουμε όλο το υπόδεντρό του. Και πράγματι, η λύση είναι σχεδόν αυτή. Με μια μικρή διαφορά: αν και ο πατέρας του \(u\) έχει μικρό υπόδεντρο (βάθους το πολύ \(C\)) τότε προτιμάμε να μαρκάρουμε τον πατέρα του \(u\), αντί για τον \(u\). Ο λόγος είναι ότι και πάλι καλύπτουμε όλο το υπόδεντρο του \(u\), αλλά και κάποιους ακόμα κόμβους. Με το ίδιο σκεπτικό, ίσως προτιμάμε τον πατέρα του πατέρα του \(u\), αν κι αυτού το υπόδεντρο είναι βάθους το πολύ \(C\), κι ούτως καθεξής. Καταλήγουμε ότι ο ιδανικός κόμβος να μαρκάρουμε είναι ένας κόμβος \(w\) με βάθος υποδέντρου το πολύ \(C\) που όμως ο πατέρας του έχει απόσταση μεγαλύτερη από \(C\) από τα φύλλα του υποδέντρου του \(w\).

Ας αποδείξουμε πρώτα ότι αν έχουμε ένα τέτοιο κόμβο \(w\), τότε θέλουμε πάντα να τον μαρκάρουμε. Παρατηρούμε ότι για να καλυφθεί το βαθύτερο φύλλο στο υπόδεντρο του \(w\), χρειάζεται να μαρκάρουμε κάποιον κόμβο, κι αυτός ο κόμβος δεν μπορεί να είναι ψηλότερα του \(w\) (επειδή ήδη ο πατέρας του \(w\) βρίσκεται σε απόσταση μεγαλύτερη από \(C\) από αυτό το φύλλο, εξ ορισμού). Αφού πρέπει οπωσδήποτε να μαρκάρουμε κάποιον κόμβο στο υπόδεντρο του \(w\), κι αφού είδαμε ότι αρκεί να μαρκάρουμε τον \(w\) για να καλύψουμε όλο το υπόδεντρό του, άρα ο \(w\) είναι πάντα η καλύτερη επιλογή.

Αφού μαρκάρουμε τον κόμβο \(w\), μπορούμε να αγνοήσουμε το υπόδεντρό του (να σβήσουμε δηλαδή τους κόμβους του υποδέντρου αυτού από το δέντρο μας) αφού πλέον τους έχουμε καλύψει όλους. Ο αλγόριθμός μας λειτουργεί ως εξής: Ξεκινάει από ένα κόμβο \(u\) (αρχικά αυτός ο κόμβος είναι η ρίζα), κι αναδρομικά κουρεύει τα υπόδεντρα των παιδιών του ώστε να έχουν βάθος το πολύ \(C\). Κατόπιν πρέπει να κουρέψει και το υπόδεντρο του \(u\) (ό,τι δηλαδή έχει απομείνει από αυτό μετά τα αναδρομικά κουρέματα) ώστε να έχει βάθος το πολύ \(C\). Για να το κάνουμε αυτό, κοιτάμε μήπως υπάρχει κάποιο παιδί \(w\) του \(u\) το οποίο μπορεί να μαρκαριστεί. Γνωρίζουμε ήδη ότι το βάθος υποδέντρου του \(w\) είναι το πολύ \(C\) λόγω της αναδρομής, επομένως πρέπει να μαρκάρουμε τον \(w\) μόνο αν το βάθος υποδέντρου του συν η απόστασή του από τον \(u\) (τον πατέρα του) δίνουν άθροισμα μεγαλύτερο του \(C\). Μπορείτε να δείτε γιατί ό,τι απομείνει έχει βάθος το πολύ \(C\);

Ο παρακάτω κώδικας υλοποιεί αυτή την άπληστη λογική.

long MinK(long u, long D) {
  long ans = 0;
  d[u] = 0;
  for (auto neigh : e[u]) {
    long weight = w[neigh];
    ans += MinK(neigh, D);
    if (d[neigh] + weight > D) ans += 1;
    else d[u] = max(d[u], d[neigh] + weight);
  }
  return ans;
}

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

#include <cstdio>
#include <vector>

using namespace std;

vector<long> d, w;
vector<vector<long>> e;

long MinK(long u, long D) {
  long ans = 0;
  d[u] = 0;
  for (auto neigh : e[u]) {
    long weight = w[neigh];
    ans += MinK(neigh, D);
    if (d[neigh] + weight > D) ans += 1;
    else d[u] = max(d[u], d[neigh] + weight);
  }
  return ans;
}

int main() {
  FILE *fi = fopen("filiki.in", "r");
  FILE *fo = fopen("filiki.out", "w");  
  long N, K, lo = 0, hi = 0, mid, par, weight;

  fscanf(fi, "%ld %ld", &N, &K);
  d.resize(N + 1);
  e.resize(N + 1);
  w.resize(N + 1);
  d[1] = 0;
  for (long i = 2; i <= N; ++i) {
    fscanf(fi, "%ld %ld", &par, &weight);
    e[par].push_back(i);
    w[i] = weight;
    d[i] = d[par] + weight;
    hi += weight;
  }

  while (lo < hi) {
    mid = (lo + hi) / 2;
    if (MinK(1, mid) + 1 <= K) hi = mid;
    else lo = mid + 1;
  }

  fprintf(fo, "%ld\n", lo);
  fclose(fi), fclose(fo);
}