MooTube (Argento)#10422
Nel suo tempo libero, il contadino John ha creato la propria piattaforma video chiamata MooTube. Su MooTube, le sue mucche possono registrare, pubblicare e trovare tanti video divertenti. Finora, le mucche hanno pubblicato video, numerati da a .
Tuttavia, il contadino John non capisce appieno come aiutare le sue mucche a trovare nuovi video che potrebbero piacere loro. Vuole implementare, per ogni video, un sistema di raccomandazione — un elenco di "video consigliati" basato sulla somiglianza con i video già visti.
Per determinare quanto due video siano simili tra loro, John introduce una metrica di rilevanza. Valuta manualmente n - 1 coppie di video e assegna a ciascuna coppia un valore di rilevanza. Sulla base di queste coppie, John costruisce una rete in cui ogni video rappresenta un vertice del grafo, e le coppie da lui selezionate sono collegate da archi con la rilevanza indicata.
Per comodità, John sceglie queste n - 1 coppie in modo tale che tra due video qualsiasi esista un unico percorso — ossia, la rete video rappresenta un albero.
Decide che la rilevanza tra due video debba essere definita come la rilevanza minima tra tutti gli archi presenti nel percorso che li collega.
Ora il contadino John vuole scegliere un valore di in modo tale che, per ogni video su MooTube, vengano mostrati tutti gli altri video la cui rilevanza rispetto ad esso sia almeno . Tuttavia, teme che un numero eccessivo di raccomandazioni possa distrarre le mucche dalla produzione di latte, quindi è importante per lui stimare con precisione quanti video verranno consigliati per diversi valori di .
Il contadino John si rivolge a Voi per avere aiuto: è necessario rispondere a diverse richieste, ciascuna delle quali contiene un valore di e il numero di un video. Per ogni richiesta, è necessario determinare quanti altri video verranno consigliati per la visione, se la rilevanza minima consentita è .
La prima riga contiene due numeri interi e q~(1 \le n, q \le 5000) — il numero di video e il numero di richieste rispettivamente.
Le successive n − 1 righe descrivono le coppie di video la cui rilevanza il contadino John valuta manualmente. Ogni riga contiene tre numeri interi p_i, q_i e r_i~(1 \le p_i, q_i \le n, 1 \le r_i \le 10^9), il che significa che i video numerati p_i e q_i sono collegati da un arco con rilevanza r_i.
Seguono righe, ciascuna delle quali descrive una richiesta del contadino John. Nella -esima riga sono contenuti due numeri interi k_i e v_i~(1 \le k_i \le 10^9, 1 \le v_i \le n) — ciò significa che nell'-esima richiesta il contadino John vuole sapere quanti video verranno consigliati per il video numero v_i, se la rilevanza minima consentita delle raccomandazioni è k = k_i.
Stampate righe. Nella -esima riga, stampate la risposta all'-esima domanda del contadino John.
Il contadino John ha stabilito i seguenti collegamenti tra i video:
I video e hanno rilevanza ,
I video e — rilevanza ,
I video e — rilevanza .
In base a questi dati, è possibile calcolare la rilevanza tra le altre coppie di video:
Video e : rilevanza = min(3, 2) = 2,
Video e : rilevanza = min(3, 4) = 3,
Video e : rilevanza = min(2, 4) = 2.
Ora consideriamo quali video verranno consigliati per le seguenti richieste:
Dal video con k = 1 verranno consigliati i video e .
Dal video con k = 3 verranno consigliati i video e .
Dal video con k = 4 non verrà consigliato alcun video.
Esempio 1