#20674: Java 解題遇到的 StackOverflowError 、TLE 問題方向


chuan.me@gmail.com (魏淳豐)

學校 : 不指定學校
編號 : 112049
來源 : [36.235.198.171]
最後登入時間 :
2023-07-13 17:30:28
b967. 4. 血緣關係 -- 2016年3月apcs | From: [124.10.224.98] | 發表日期 : 2020-02-18 15:51

實作概念:
建構關聯樹(每個節點紀錄下一層的關聯節點與父節點)。使用 DFS 進行節點走訪。
因為 DFS 的特性,在走訪過程,可以由葉節點,往回累計由葉節點回推的深度。

在每個節點 i 紀錄該節點向下延伸最長的兩段長度和 D(i) = top1Length(i)+top2Length(i)。

該題答案要找的答案,就是所有節點中最大的長度和   max( D(i) )

1. 本題一開始使用函式遞迴實作 DFS ,在測資4 ,因為呼叫太多層會引發 StackOverflowError 問題。
    解法:使用 Stack 堆疊 + 迴圈實作 DFS,不用遞迴函示實作。
2. 測資 4 ,使用 Scanner 讀取資料會遇到 TLE 問題。
    解法:在讀取資料改用 BufferedReader 會快很多。

 
ZeroJudge Forum