Wioska

W zadaniu mamy dane drzewo o n wierzchołkach. Dla danej permutacji wierzchołków p definiujemy jej koszt jako suma po wszystkich wierzchołkach v z długości ścieżek od v do p[v]. Należy znaleźć permutację, która minimalizuje tę sumę, oraz taką, która ją maksymalizuje.

Permutacja minimalizująca sumę

Jak zrobimy przejście DFS po drzewie i weźmiemy permutację cykliczną, która przesuwa wierzchołki w kolejności odwiedzania ich DFS-em, to dla n wierzchołków suma tras będzie wynosić 2*(n-1).

Jeśli więc podzielimy drzewo na k spójnych kawałków wielkości co najmniej 2, i w każdym z nich zrobimy obejście DFS, to sumarycznie będziemy mieli 2*(n-k).

Okazuje się, że jeśli k będzie największe możliwe (co można również wyznaczyć bardzo prostym programowaniem dynamicznym), to wtedy odpowiedź jest minimalna. Algorytm będzie działał w czasie liniowym:

const int N = 110000;
int n;
vector<int> adj[N];
int col[N];
int C;
int total_col;
vector<int> colors[N];
int perm[N];

int dfs(int v, int par) {
  int siz = 1;
  col[v] = C++;
  ++total_col;
  int cf = -1;
  for (int u : adj[v]) if (u != par) {
    if (!dfs(u, v)) {
      ++siz;
      col[u] = col[v];
      --total_col;
    } else {
      cf = col[u];
    }
  }

  if (siz == 1) {
    if (par == -1) {
      col[v] = cf;
      --total_col;
    }
    return 0;
  }
  return 1;
}

void dfs2(int v, int par) {
  colors[col[v]].push_back(v);
  for (int u : adj[v]) if (u != par) {
    dfs2(u, v);
  }
}

int main() {
  scanf("%d",&n);
  REP(i,n-1) {
    int a,b; scanf("%d%d",&a,&b); --a; --b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }

  C = 1;
  dfs(0, -1);

  int len = 2*(n-total_col);
  printf("%d 0\n", len);

  dfs2(0, -1);

  REP(c,C) {
    vector<int>& cc = colors[c];
    int m = cc.size();
    REP(i,m) perm[cc[i]] = cc[(i+1)%m];
  }

  REP(i,n) printf("%d ",perm[i]+1);
  printf("\n");
  REP(i,n) printf("%d ",i+1);
  printf("\n");

}

Permutacja maksymalizując sumę

Rozważmy dowolną krawędź drzewa i zastanówmy się, ile maksymalnie ścieżek może przechodzić tą krawędzią? Usunięcie krawędzi rozbija nam drzewo na dwa poddrzewa: jedno ma s wierzchołków, a drugie ma n-s wierzchołków. W każdym wierzchołku zaczyna się dokładnie jedna ścieżka i dokładnie jedna ścieżka kończy; zatem w pierszym poddrzewie możemy mieć co najwyżej s początków ścieżek, a w drugim co najwyżej n-s końców. Zatem maksymalna liczba ścieżek, które zaczynają się w pierwszym poddrzewie, a kończą w drugim, wynosi min(s,n-s). Symetryczny argument jest dla ścieżek w drugą stronę.

Zatem maksymalny koszt permutacji to suma 2*min(s,n-s) po wszystkich krawędziach drzewa. Okazuje się, że możemy osiągnąć to maksimum.

Rozważmy centroid drzewa v, czyli wierzchołek, którego usunięcie rozbija drzewa na poddrzewa rozmiaru nie większego niż n/2. Podzielmy wierzchołki drzewa na zbiory: każde poddrzewo z rozbicia będzie jednym zbiorem, plus mamy dodatkowy zbiór zawierający wierzchołek v. Pokażemy, że permutacja p będąca cyklem, w którym każde dwa kolejne wierzchołki będą z różnych zbiorów, ma maksymalny koszt.

Musimy w tym celu pokazać, że przez każdą krawędź przechodzi 2*min(s,n-s) ścieżek. Jeśli ta krawędź łączy centroid v z jakimś innym u (rozmiaru s), to poddrzewo u ma nie więcej niż n/2 wierzchołków, zatem 2*min(s,n-s) = 2*s. Ale dla dowolnego wierzchołka w z tego poddrzewa wierzchołek p[w] należy do innego zbioru, zatem ścieżka z w przechodzi krawędzią u-v (analogicznie dla ścieżek w drugą stronę).

Jeśli krawędź nie dotyka centroidu, to łączy wierzchołki u1 i u2 znajdujące się w jednym zbiorze. Niech u2 będzie bliżej centroidu v. Wtedy min(s,n-s) jest rozmiarem poddrzewa u1 i każda ścieżka z tego poddrzewa musi przechodzić przez centroid, zatem przechodzi przez krawędź u1-u2.

W poniższym kodzie najpierw znajdujemy centroid i podział na zbiory, a następnie kolejność zbiorów (pomocniczą funkcją construct_order) i w końcu cykl:

const int N = 110000;
int n;
vector<int> adj[N];
ll len;
int siz[N];
int centroid;
int perm[N];
vector<vector<int>> cols;
int cycle[N];

void dfs(int v, int par) {
  siz[v] = 1;
  int ms = -1;
  for (int u : adj[v]) if (u != par) {
    dfs(u, v);
    siz[v] += siz[u];
    len += 2*min(siz[u], n-siz[u]);
    ms = max(ms, siz[u]);
  }
  if (2*max(ms, n-siz[v]) <= n) {
    centroid = v;
  }
}

void dfs2(int v, int par) {
  cols.back().push_back(v);
  for (int u : adj[v]) if (u != par) {
    dfs2(u, v);
  }
}


int main() {
  scanf("%d",&n);
  REP(i,n-1) {
    int a,b; scanf("%d%d",&a,&b); --a; --b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }

  dfs(0, -1);

  printf("0 %lld\n", len);

  cols.push_back({ centroid });
  for (int u : adj[centroid]) {
    cols.push_back(vector<int>());
    dfs2(u, centroid);
  }

  vector<int> counts;
  for (auto& c : cols) counts.push_back(c.size());
  vector<int> order = construct_order(counts);

  REP(i,n) {
    cycle[i] = cols[order[i]].back();
    cols[order[i]].pop_back();
  }

  REP(i,n) perm[cycle[i]] = cycle[(i+1)%n];

  REP(i,n) printf("%d ",i+1);
  printf("\n");
  REP(i,n) printf("%d ",perm[i]+1);
  printf("\n");
}

Na koniec musimy pokazać dowód lematu, że jeśli mamy multizbiór, w którym żaden element nie pojawia się więcej niż połowę liczby elementów, to można ustawić je w cykl, że sąsiadnie elementy są różne.

Na początek rozważamy przypadek szczególny, w którym jeden z elementów pojawia się dokładnie połowę razy. Ale wtedy można go ustawić na pozycjach parzystych, a pozostałe elementy dowolnie na pozycjach nieparzystych.

Zatem teraz każdy element występuje mniej niż połowę razy. Algorytm jest prosty: umieszczamy elementy na cyklu grupami równych elementów. Idziemy po kolei pozycjami parzystymi, a gdy już się skończą idziemy od początku pozycjami nieparzystymi. Jedyny problem może być z grupą elementów, których część została umieszczona na sufiksie pozycji parzystych, a część na prefiksie pozycji parzystych. Ale ponieważ tych elementów jest mniej niż połowa, więc pierwsza pozycja parzysta nie będzie sąsiadować z ostatnią nieparzystą.

Kode jest prosty i znajduje cykl w czasie liniowym od liczby elementów:

vector<int> construct_order(const vector<int>& counts) {
  int total = 0, m = counts.size();
  REP(i,m) total += counts[i];
  vector<int> ans(total);
  REP(i,m) {
    assert(2*counts[i] <= total);
    if (2*counts[i] == total) {
      REP(j,total/2) ans[2*j] = i;
      int j = 1;
      REP(k1,m) if (k1 != i) REP(k2,counts[k1]) {
        ans[j] = k1;
        j += 2;
      }
      return ans;
    }
  }

  int j = 0;
  REP(k1,m) REP(k2,counts[k1]) {
    ans[j] = k1;
    j += 2;
    if (j >= total) j = 1;
  }
  return ans;
}

Cały algorytm działa zatem w czasie $O(n)$.