Bài A

Thuật toán:

Chúng ta sẽ đến với 1 cấu trúc dữ liệu là bảng thưa

Gọi ~trace[x][i]~ là cha của nút ~x~ khi dfs từ ~1~ và độ cao từ nó đến ~x~ là ~2^i~

Ví dụ ~trace[x][0]~ là cha trực tiếp của đỉnh ~x~ khi dfs từ ~1~

Vậy chúng ta sẽ tìm ~trace[x][i]~ như thế nào ?

Chúng ta thấy rằng ~2^{i-1} + 2^{i-1} = 2^i~ ~(1)~

Giả sử: Hiện tại ta có cha của ~x~ mà có độ cao đến ~x~ là ~2^{i-1}~ và ta gọi nó là ~par~ (~par=trace[x][i-1]~)

Áp dụng ~(1)~ ta có thể tính ~trace[x][i]~ bằng cách từ ~par~ chúng ta. Tìm cha của ~par~ mà cách ~par~ 1 khoảng ~2^{i-1}~ ( Tìm ~trace[par][i-1]~ )

Khi đó ~trace[par][i-1]~ chính là ~trace[x][i]~ cần tìm:

Vì dồ thị chỉ có ~10^5~ đỉnh thì khi đó trường hợp xấu nhất là đỉnh x cần đi qua hết ~10^5~ đỉnh với mỗi ~trace[x][i]~ thì ~i~ lớn nhất là bao nhiêu ~(2)~

Ta thấy, vì ~trace[x][i]~ là đỉnh cha cách đỉnh x độ cao ~2^i~ mà trong trường hợp xấu nhất như trên thì lúc này ta cần tìm k mà ~2^k=10^5~

Áp dụng Logarit thì ta có ~k=log_2(10^5) \Rightarrow k~ gần bằng ~17~ nên chúng ta có thể suy ra đáp số ~(2)~ cần tìm là ~17~

CODE:

const int LOG=17;
void sprase_table()
{
    for(int i=1;i<=LOG;i++)
    {
        for(int node=1;node<=n;node++)
        {
            int par=trace[node][i-1];
            if(par!=-1)// Nếu x có nút cha cách nó độ cao 2 ^(i-1)
            {
                trace[node][i]=trace[par][i-1];
            }
        }
    }
}