c149. B. 新鮮人小祥的套件難題 - 大魏線上解題系統

Content

"小祥是個程式天才，因此他高中畢業後便決定出國深造，來到遙遠的ㄏㄏ國，並進入當地最頂尖的國立天才大學（National Tiantsai University, NTU）就讀"

經過大學有趣又充實的生活後，小祥順利進入了當地最頂尖的科技公司任職。身為一個大天才，他理所當然被分派到整個公司最重要的部門：關鍵系統套件維護組，負責維護和升級公司內部龐大的軟體系統。

這個系統由若干個相互依賴的套件所組成，其結構呈現一棵以核心套件為根的樹狀結構。除了最上層的核心套件外，每一個套件都依賴一個 母套件 才能正常運作。如果某個母套件發生錯誤，不僅它自己會失效，所有依賴它的子套件也會無法運行，甚至可能導致整個系統崩潰。

對於剛入職的小祥來說，因為沒有實際面對過如此龐大且複雜的系統，小祥決定先進行全面的風險評估。他整理出了系統中所有的套件依賴關係，發現每個套件都有自己的編號（其中核心套件的編號為 $1$），而公司儲存套件依賴的方式是紀錄 每個套件的母套件編號（除了核心套件）。現在小祥想要知道，每個套件會有多少個子套件會直接或間接受到它的影響，以便衡量修改一個套件會帶來的潛在影響範圍，但由於套件的資料實在是太多了，因此請你寫一筆程式幫助他解決這個問題。

※Update:

2025/09/13 因 zerojudge 系統遞迴層數限制，正確的程式可能無法通過第 0,5,12 筆測資。

Input

$N$
$B_1$ $B_2$ $B_3$ $\dots$ $B_{N-1}$

$1\le N\le 2 \times 10^5$
$N$ 表示 總套件數
$1\le B_i\le N \ (1 \le i < N)$
$B_i$ 表示編號 $i+1$ 的套件的母套件編號

Output

$ans_1$ $ans_2$ $\dots$ $ans_N$

輸出 $N$ 個整數，其中 $ans_i$ 表示編號為 $i$ 的套件的子套件數量。

Sample Input #1

5
1 1 2 3

Sample Output #1

4 1 1 0 0

Sample Input #2

7
1 2 1 2 4 5

Sample Output #2

6 3 0 1 1 0 0

Sample Input #3

6
1 2 3 4 5

Sample Output #3

5 4 3 2 1 0

測資資訊：

記憶體限制： 256 MB
公開測資點#0 (5%): 1.0s , <10M
公開測資點#1 (5%): 1.0s , <1K
公開測資點#2 (5%): 1.0s , <1K
公開測資點#3 (5%): 1.0s , <1K
公開測資點#4 (5%): 1.0s , <1M
公開測資點#5 (5%): 1.0s , <10M
公開測資點#6 (5%): 1.0s , <10M
公開測資點#7 (5%): 1.0s , <1K
公開測資點#8 (5%): 1.0s , <1K
公開測資點#9 (5%): 1.0s , <1K
公開測資點#10 (5%): 1.0s , <10M
公開測資點#11 (5%): 1.0s , <1K
公開測資點#12 (5%): 1.0s , <10M
公開測資點#13 (5%): 1.0s , <1M
公開測資點#14 (5%): 1.0s , <1M
公開測資點#15 (5%): 1.0s , <1M
公開測資點#16 (5%): 1.0s , <1M
公開測資點#17 (5%): 1.0s , <1M
公開測資點#18 (5%): 1.0s , <1M
公開測資點#19 (5%): 1.0s , <1M

Hint ：

在範例 $1$ 中：套件 $1$ 共有 $4$ 個子套件 $2,3,4,5$，套件 $2$ 共有 $1$ 個子套件 $4$，套件 $3$ 共有$1$ 個子套件 $5$，而套件 $4,5$ 沒有任何子套件。

範例 2 的樹狀結構圖如下：

Tags:

DFS tree 圖論遞迴

出處:

114學年校內能競選拔 [管理者： jackhuang(fijjj) ]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」