Nhận xét 1: Sau khi được người dân chỉ điểm, ta có thể thu gọn khu vực tìm kiếm về một trong những cây con tạo ra bởi việc xóa đỉnh được chọn trong lượt đó khỏi cây.

Xét một phương án bất kì, gọi đỉnh đầu tiên ta chọn của một cây là gốc của cây đó. Từ đây ta dựng một cây như sau:

• Xoá gốc của cây hiện tại ra khỏi cây.
• Nối gốc hiện với gốc của các cây con được tạo ra.
• Thực hiện quá trình này trên các cây con.

Gọi cây tạo bởi quá trình này là ~D~ và cây ban đầu là ~T~. Gọi ~f~ là một hàm gán cho mỗi đỉnh ~v~ của ~T~ một giá trị ~f(v)~ nguyên dương thỏa mãn tính chất: nếu ~u~ là cha của ~v~ trên cây ~D~ thì ~f(u)>f(v)~. Kết quả của bài toán sẽ là giá trị nhỏ nhất của ~\max\{f_v\}~ trong tất cả các cây ~D~ và các hàm ~f~ ứng với nó.

Ta có thể chứng minh điều kiện cần và đủ để một hàm ~f~ bất kì tương ứng với một cây ~D~ là: trên đường đi từ ~u~ đến ~v~ trên cây ~T~ với ~u,v~ thoả mãn ~f(u)=f(v)~ tồn tại ít nhất một đỉnh ~w~ sao cho ~f(w)>f(u)~. ~(*)~

Xét một cách xây dựng hàm ~f~ như sau:

• Chọn một đỉnh bất kì làm gốc của cây ~T~ (đây chỉ là gốc để tính toán, không liên quan đến gốc được định nghĩa ở phía trên), ta sẽ tính ~f~ theo chiều giảm dần của độ sâu.
• Các lá được gán giá trị ~f(v)=1~.
• Các đỉnh không phải lá được gán giá trị ~f(u)~ nhỏ nhất có thể sao cho điều kiện ~(*)~ được thỏa mãn.

Bước thứ ba có thể thực hiện như sau:

• Xét đỉnh ~u~, một giá trị ~f(v)~ nằm trong cây con gốc ~u~ được gọi là lộ diện nếu ~f(v)~ lớn hơn tất cả các giá trị khác trên đường đi từ ~v~ đến ~u~.
• Gọi ~S(u)~ là tập tất cả các giá trị khác nhau lộ diện với đỉnh ~u~.
• ~f(u)=x~ sẽ là giá trị nhỏ nhất thỏa mãn:
  • ~x~ không lộ diện với đỉnh ~u~.
  • Nếu tồn tại giá trị ~y~ lộ diện với ít nhất hai con của ~u~ thì ~x> y~.
• Loại bỏ tất các giá trị bé hơn ~f(u)~ và thêm ~f(u)~ vào trong ~S(u)~.

Xét ví dụ ứng với hình bên:

• ~f(7)=1,S(7)=\{1\}~.
• ~f(6)=2,S(6)=\{2\}~.
• ~f(5)=1,S(5)=\{2,1\}~.
• ~f(3)=3,S(3)=\{3\}~.
• ~f(2)=1,S(2)=\{3, 1\}~.
• ~f(4)=1,S(4)=\{1\}~.
• ~f(1)=2,S(1)=\{3,2\}~.
• ~f(0)=1,S(0)=\{3,2,1\}~.

Xét hai tập ~X~ và ~Y~, ta nói ~X\ge Y~ nếu sắp xếp giảm dần cả hai tập thì phần tử đầu tiên khác nhau của ~X~ sẽ lớn hơn hoặc ~Y~ nằm gọn trong ~X~. Ví dụ ~\{5,4,1\}>\{5,3,2\}~ hoặc ~\{5,4,3\}>\{5,4\}~.

Ta sẽ chứng minh với mọi đỉnh ~u~ thì ~S(u)~ được xây dựng theo cách như trên đạt giá trị nhỏ nhất.

Nhận xét 2: Việc tăng giá trị ~f~ ở một đỉnh nào đó sẽ không khiến ~S~ ở một đỉnh khác nhỏ đi.

Từ nhận xét này kết hợp với việc ta luôn tìm ~f~ nhỏ nhất có thể ở mỗi đỉnh suy ra được điều phải chứng minh. Từ đây ta suy ra ~\max\{f_v\}~ đạt giá trị nhỏ nhất.

Trong bài này ta luôn có ~f(v)\le log_2(n)+1~ (bằng cách luôn chọn centroid của một cây) do đó ta có thể dùng một số nguyên để lưu ~S~ tương ứng với một dãy bit.

Độ phức tạp của thuật toán sẽ là ~O(n\cdot log_2n)~ hoặc ~O(n)~ tuỳ vào cách cài đặt.

Code mẫu

#include <bits/stdc++.h>
using namespace std;

const int MAX = 100000;
int N, n;
vector<int> graph[MAX];
int label[MAX];

int dfs(int node)
{
    label[node] = -1;
    int used = 0, more = 0;
    for (int i = 0; i < graph[node].size(); ++i)
    {
        int next = graph[node][i];
        if (!label[next])
        {
            int next_used = dfs(next);
            more |= used & next_used;
            used |= next_used;
        }
    }

    // find nearest biggest power of 2
    more |= more >> 1;
    more |= more >> 2;
    more |= more >> 4;
    more |= more >> 8;
    more |= more >> 16;
    ++more;

    int possible = (~used) & (-more);
    label[node] = possible & (-possible);

    used |= label[node];
    used &= -label[node];
    return used;
}

int main()
{
    scanf("%d", &N);
    for (int i = 1; i < N; ++i)
    {
        scanf("%d", &n);
        graph[i].push_back(n);
        graph[n].push_back(i);
    }
    // label vertices with powers of 2
    dfs(0);
    // find the biggest label we have used and output log_2(label)+1
    int maximum = *max_element(label, label+N), result = 0;
    while (maximum)
    {
        ++result;
        maximum >>= 1;
    }
    printf("%d\n", result);

    return 0;
}