+ محدودیت زمان: ۳ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- معلم حنا هدیه تولد به او یک درخت ریشه‌دار $n$ راسی داده که ریشه آن راس شماره $1$ است. روی راس شماره $i$ آن عدد $a_i$ نوشته‌ شده‌‌است. حنا بعد از یادگرفتن الگوریتم [جستجوی عمق اول](https://fa.wikipedia.org/wiki/%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85_%D8%AC%D8%B3%D8%AA%D8%AC%D9%88%DB%8C_%D8%A7%D9%88%D9%84_%D8%B9%D9%85%D9%82) تکه کد زیر را نوشته است. ``` b := an array of length n time := 1 procedure DFS(T, a, v): b[time] = a[v] time += 1 label v as visited for u in T.neighbors(v) do: if not visited[u] do: DFS(T, a, u) end if end for end procedure procedure countInversions() DFS(T, a, 1) return number of inversions in the array b /* Number of inversions in the array b is the number of distinct pairs (i, j) such that 1 <= i < j <= n and b[i] > b[j] */ end procedure ``` حنا می‌خواهد تابع `countInversions‍` را فراخوانی کند. او می‌داند که خروجی این تابع به ترتیب همسایه‌های هر راس در تابع `DFS‍` وابسته است. به او کمک کنید، کمینه خروجی ممکن این تابع را پیدا کند. در واقع حنا می‌خواهد طوری ترتیب همسایه‌های رئوس را انتخاب کند که تعداد نابه‌جایی‌های آرایه `b` کمینه بشود. منظور از نابه‌جایی تعداد جفت‌های $1 \le i < j \le n$ است که $a_i > a_j$ باشد. # ورودی در سطر اول ورودی عدد $n$ آمده‌است. در سطر دوم، اعداد $a_1, a_2, ..., a_n$ به ترتیب آمده‌اند. در سطر سوم، اعداد $p_2, p_3, ..., p_n$، به ترتیب آمده‌اند که $p_i$ پدر راس شماره $i$ درخت معلم است. $$ 1 \leq n \leq 1 \, 000 \, 000 $$ $$ 0 \leq a_i \leq 2 $$ $$ 1 \leq p_i < i $$ # خروجی در سطر اول خروجی، کمینه خروجی تابع `countInversions` را چاپ کنید. # مثال # ورودی نمونه ۱ ``` 6 0 0 2 0 0 2 1 2 3 2 2 ``` # خروجی نمونه ۱ ``` 1 ``` # ورودی نمونه ۲ ``` 8 0 1 1 2 1 0 1 2 1 2 2 1 1 2 3 ``` # خروجی نمونه ۲ ``` 0 ``` # ورودی نمونه ۳ ``` 10 2 0 1 1 1 2 1 0 0 0 1 2 2 1 5 5 5 5 5 ``` # خروجی نمونه ۳ ``` 16 ``` <details class="blue"> <summary> راهنمایی ۱ </summary> ابتدا سعی کنید تابعی برای مقایسه‌ی بین دو تا از بچه‌های هر راس پیدا کنید که بگوید بهتر است اول وارد کدام بچه شود، سپس ثابت کنید این تابع، تابعی مناسب برای مرتب‌سازی بچه‌های یک راس از درخت است. </details>