La mia idea è piuttosto semplice: per ogni nodo del grafo lo metto come root dell’albero e parte una dfs dal nodo tenendo, ad ogni chiamata, la distanza dalla base al nodo corrente; se il nodo corrente è una filiale allora aggiungo la sua distanza alla somma. Alla fine il nodo preso come root che ha la somma minore è la risposta. Il tutto credo ha complessità O(N^2) e va in TLE.
Ho pensato di calcolare in qualche modo il numero di filiali sotto il nodo corrente e se è 0 fermare la ricerca ma non sono riuscito perché N e K arrivano fino a 10^6 e dubitavo migliorasse le cose.
C’è una tecnica particolare per risolvere questo problema o ci sono osservazioni che non ho colto?