物理老師今天似乎不想上課,一進教室就開始講實驗的事。而這次,他為了讓我們接觸一些電學的相關實驗但要壓低成本,選擇了 Arduino 。
毫無疑問,作為一個電學實驗的器材, Arduino 具有算是良好的自訂性、可接受的精確度,以及幾乎為 0 的成本(建中校內有足夠的 Arduino)。然而,作為一個程式人,聽到 Arduino 可以拿來跑基本的程式時當然想要拿 Arduino 跑一些怪東西。
同學首先想到的是語音辨識:利用 RNN 訓練偵測國文老師的聲音。因為國文老師上課有小十字的習慣,當附近的人被抽到時自己就得站起來,而最慢站起來的那一個就必須回答問題。而身為反應總是慢半拍的人,自然會想要一個提示站起來的東西;然而,當他查看 Arduino 的內存時就立馬放棄了 - 是 KB 等級的。
我不知道他在想什麼,那板子上很顯然沒有內存的樣子,不過這倒是讓我想起了人類史上第一張黑洞的照片,以及過往對黑洞的模擬。

克里斯多福·諾蘭(Christopher Nolan)作為知名大導演,其一大特色就是能不用 CG 就不用 CG ,在〈星際效應〉(Interstellar)中,黑洞是少數使用電腦模擬出來的場面。雖然是用電腦模擬出來的場面,但是大量參考了真實的數據,以及和天文學家合作寫出演算法模擬真實的場景。這些努力使得他模擬出的黑洞幾乎接近於之後 NASA 給出的圖片,震驚了觀眾們。

而這個過程同樣需要耗費大量的算力(主要是浮點運算),更別提內存,只為了求一個精確的結果。事實上很多物理以及化學上的模擬,例如流體以及大氣,所需要的算力都相當誇張,不斷發展的技術正在讓這方面有突破性的成長。
讓我們回頭關注星際效應吧。星際效應是一部 2014 年的科幻電影,故事主要講述人類穿越蟲洞尋找新家園。因為其精美的視覺特效以及貼近真實的科學理論而廣受讚譽。而其中有一個動人的片段,就是男主角庫柏在黑洞中找尋正確時空,並想辦法傳輸黑洞資料的畫面。
這段找尋時空的畫面雖然男主角說是因為愛,但是實際上它還是遵循一些規則的。首先有一個什麼改變都沒有發生的「原始時空」,接著每當時空裡的人做出一次決定,就會產生不只一種可能性而分裂成兩個或以上的「衍伸時空」。這些分裂後的時空不會彼此影響,也不會有衍伸時空最終衍伸出相同時空等荒謬結論,稍微降低了分析的複雜度。而這些時空在未來人類的幫助之通通陳列在庫柏眼前,也就是說,庫柏可以同時看到原始時空以及它所衍伸的衍伸時空們,以及衍伸時空所衍伸的空…以此類推。
為了分析時空的資料。庫柏為了每個時空定了一個可能性,而可能的關係必須符合:
- 在同一個時空分支(任何原始時空-衍伸時空-衍伸時空的衍伸...的關係)上按照分支上從原始時空衍伸的順序挑選出一些時空,這些時空可以不用連續
- 這些被挑選出的時空的可能性必須嚴格遞增
現在,未來的人類已經為你陳列出所有時空了,想辦法找到最長的可能關係吧。
第一行有一個數 $n$ ,代表有 $n$ 個時空,編號 $1, 2, ...n$,其中編號 1 的時空是原始時空。
第二行有 $n$ 個數,分別代表每個時空的可能性 。
接下來有 $n - 1$ 行,每行有兩個數 $u, v$ ,代表 $u, v$ 之間有時空間的因果關係(時空 - 衍伸時空)。
保證沒有重複的關係且全部時空都被關係連接著。
$1 \leq n \leq 3 \times 10 ^ 5$
$1 \leq p_i \leq 10 ^ 9$
請輸出最長可能關係的長度
5 1 3 2 4 5 1 2 1 4 2 3 4 5
3
註:時空的衍伸關係和可能性是獨立的
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 範例測資 | 0 |
| 2 | 1~10 | 關係為 $(1, 2), (2, 3)...(n - 1, n)$ | 30 |
| 3 | 0~25 | 無其他限制 | 70 |