Bosses

Rozwiązanie

Załóżmy, że jeżeli mamy już kształ drzewa, to przypisanie wag, żeby zminimalizować ich sumę, jest bardzo proste. Zaczynamy od liści, którym przypisujemy $1$, a następnie każdy wierzchołek wewnętrzny ma wagę równą sumie wag dzieci plus $1$.

Popatrzmy, jak zmieni się sumaryczna waga, gdy do takiego drzewa dodamy nowy liść na głębokości $L$ (zakładamy, że korzeń jest na głębokości 1). Liść doda $1$ do sumarycznej wagi, następnie jego ojciec też doda $1$ i tak dalej: każdy wierzchołek na ścieżce do korzenia doda $1$, zatem sumarycznie waga wzrośnie o $L$. Tak więc widać, że całkowita waga to suma głębokości wszystkich wierzchołków. Zatem opłaca się, by wierzchołki były położone jak najbliżej korzenia.

Z ograniczeń na dane wynika, że rozwiązanie $O(nK)$, gdzie $K = \sum k_i$ jest akceptowalne. To pozwala nam na przeiterowanie się po wszystkich wyborach korzenia drzewa.

Mając wybrany korzeń $v_r$, resztę wierzchołków można podczepiać zachłannie. Na początek możemy podczepić wszystkie wierzchołki, dla których $v_r$ może być ojcem. Następnie możemy podczepić wszystkie wierzchołki, dla których te nowo podczepione mogą być ojcem (a nie zostały podczepione wcześniej). I tak dalej.

Wystarczy zatem dla każdego wierzchołka $v$ pamiętać listę tych, które akceptują $v$ jako ojca i zrobić prostego BFS-a w czasie $O(K)$:

const int N = 5100;
int n,k,v;
vector<int> child[N];
int level[N],q[N],qe,qb;

int main() {
  scanf("%d",&n);
  REP(i,n) {
    scanf("%d",&k);
    REP(j,k) {
      scanf("%d",&v);
      child[v-1].push_back(i);
    }
  }

  int best = n*n;
  REP(root,n) {
    REP(i,n) level[i] = -1;
    level[root] = 1;
    int total = 1;
    qe = qb = 0;
    q[qe++] = root;
    while (qe != qb) {
      int v = q[qb++];
      for (int u : child[v]) if (level[u] == -1) {
        level[u] = level[v] + 1;
        total += level[u];
        q[qe++] = u;
      }
    }
    if (qe == n) {
      best = min(best, total);
    }
  }

  printf("%d\n", best);
}