+ محدودیت زمان: ۳ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- معلم حنا هدیه تولد به او یک درخت ریشه‌دار $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 ```

حل سؤال در بانک سؤالات