هش درخت¶

تبدیل به برابری دو درخت ریشه دار¶

فرض کنید می دانیم راس \(u_1\) از درخت \(T_1\) قرار است برابر با راس \(u_2\) از درخت \(T_2\) شود. آنگاه می توانیم برابر بودن دو درخت ریشه دار را بررسی کنیم که به نظر می رسد ساده تر از مسئله فعلی باشد.

پس حالا اگر بتوانیم مسئله برابری دو درخت ریشه دار \(n\) راسی را در \(O(f(n))\) حل کنیم راه حلی داریم که مسئله فعلی را در \(O(n \times f(n))\) حل می کند. تنها کافیست \(u_1\) را یک راس ثابت در نظر بگیریم و روی \(u_2\) حالت بندی کنیم.

ایده کلیدی در اینجا این است که \(u_1,u_2\) را با ویژگی خاصی انتخاب کنیم که تعداد راس های درخت با این ویژگی کم باشد. مثلا اگر \(u_1\) را یک برگ در نظر بگیریم آنگاه \(u_2\) نیز باید برگ باشد پس به جای \(n\) بار حالت بندی روی \(u_2\) کافی است به تعداد برگ های \(T_2\) بار حالت بندی کنیم.

در قسمت های قبل یاد گرفتیم که هر درخت حداکثر 2 سنتروید دارد. در نتیجه اگر ویژگی مورد نظر را سنتروید بودن در نظر بگیریم کافی است \(u_1\) را یکی از سنتروید های درخت \(T_1\) در نظر بگیریم و برای \(u_2\) روی تمام سنتروید های درخت \(T_2\) حالت بندی کنیم (که حداکثر 2 تا هستند). پس توانستیم مسئله را در \(O(f(n))\) حل کنیم.

حل مسئله برابری دو درخت ریشه دار¶

فرض کنید \(r_1\) ریشه درخت \(T_1\) و \(r_2\) ریشه درخت \(T_2\) باشد و حالا می خواهیم برابری این دو درخت را بررسی کنیم. در ابتدا اگر تعداد بچه های \(r_1,r_2\) مساوی نباشند که دو درخت به وضوح نابرابرند. در صورت مساوی بودن تعداد بچه ها باید بفهمیم که هر کدام از بچه های \(r_1\) به کدام یک از بچه های \(r_2\) متناظر شده است. اگر این موضوع را بفهمیم می توان به صورت بازگشتی مسئله را حل کرد به اینصورت که به ازای تمام بچه های \(r_1\) باید برابری زیردرخت آن با زیردرخت راس متناظرش در درخت \(T_2\) را بررسی کنیم.

به عبارتی باید دنباله بچه های \(r_1,r_2\) را به طریقی جایگشت بدهیم سپس به ازای هر \(i\) برابری زیردرخت بچه \(i\) ام \(r_1,r_2\) را بررسی می کنیم.

حالا از این ایده استفاده می کنیم که ترتیب بچه های هر راس را بر حسب ویژگی خاصی مرتب کنیم. در اینصورت دیگر نیاز نیست تمام جایگشت های بچه های \(r_1,r_2\) را بررسی کنیم و تنها کافیست ترتیب فعلی را بررسی کنیم.

به هر درخت ریشه دار مثل \(T\) با ریشه \(r\) یک دنباله از پرانتزگذاری ها را نسبت می دهیم. به اینصورت که ابتدا زیردرخت مربوط به بچه های \(r\) را به صورت بازگشتی حساب می کنیم سپس بچه های \(r\) را بر اساس ترتیب کتابخانه ای (lexicographical order) رشته آن ها مرتب می کنیم. این همان ترتیب ثابتی است که می خواستیم به بچه های هر راس نسبت بدهیم. در نهایت دنباله پرانتز گذاری \(T\) به صورت \(S = (S_1S_2...S_k)\) می باشد که \(S_i\) ها دنباله پرانتزگذاری مربوط به زیردرخت بچه \(i\) ام \(r\) است.

می توانید بررسی کنید که دو درخت ریشه دار با هم برابر هستند اگر و تنها اگر دنباله پرانتزگذاری نسبت داده شده به آن دو با هم برابر باشند.

محاسبه هش درخت ریشه دار¶

از آنجایی که کار کردن با یک رشته (چسباندن دو رشته به هم یا چک کردن تساوی دو رشته) نیاز به \(O(n)\) عملیات دارد ما را به فکر می اندازد تا به جای اینکه به هر راس یک رشته نسبت دهیم، به هر راس یک عدد نسبت دهیم که هر عدد نماینده یک رشته باشد!

پس از منطق بالا استفاده می کنیم و به عدد مربوط به هر راس را به اینصورت به دست خواهیم آورد. ابتدا اعداد بچه ها را به دست می آوریم سپس آن ها را مرتب کرده و با فرض اینکه \(H_1,...,H_k\) باشند عدد ما برابر با \(H = 1 + \sum H_i \times P^i\) به پیمانه \(M\) خواهد بود که \(M, P\) دو عدد اول تصادفی هستند. به این تکنیک هش کردن (hash) می گویند. از آنجایی که \(M,P\) اعداد تصادفی هستند می توان فرض کرد اعداد به دست آمده تصادفی هستند و احتمال اینکه به دو درخت متفاوت اعداد یکسان نسبت دهیم بسیار ناچیز خواهد بود. (برای اطمینان می توان با \(M,P\) های بیشتر این کار را انجام داد تا احتمال خراب شدن کار کم و کمتر شود).

پیاده سازی الگوریتمی که بیان کردیم به این صورت می باشد :

const int maxn = 1e5 + 10, P = 101, M = 1e9 + 9;

vector <int> v[maxn];

int calc(int u, int par = -1){
    vector<int> vec;
    for(int y : v[u]){
            if(y != par)
            vec.push_back(calc(y, u));
    }
    sort(vec.begin(), vec.end());
    int H = 0;
    for(int x : vec)
          H = (1ll * H * P + x) % M;
    H = (1 + H) % M;
    return H;
}

int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n - 1; i++){
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    cout << calc(1) << "\n"; // hash derakht rishe dar az 1
    return 0;
}