嗨嗨嗨 來了噢

這道題耗子可是跟 @清塵_傾城 一起肝了一下午才肝出來的（

請(qǐng)看我們滴血壓

先上代碼awa

主要思路在代碼注釋講解

這道題要卡常的（

這里有幾個(gè)主要的優(yōu)化方向：

1. 第一次我是寫的兩個(gè)搜索 一次是累加 一次是求此節(jié)點(diǎn)的父親 但 @清塵_傾城 把2個(gè)搜索合并 不用求父親 往下搜的時(shí)候直接帶上上次搜的節(jié)點(diǎn)就是下面要搜節(jié)點(diǎn)的父親 這樣就可以省下幾乎一半的時(shí)間

2. 這里涉及到鄰接表實(shí)現(xiàn)方式的速率問題

   結(jié)構(gòu)體+鏈?zhǔn)角跋蛐?< 結(jié)構(gòu)體+靜態(tài)鏈表<靜態(tài)鏈表<vector<動(dòng)態(tài)鏈表

   實(shí)測(cè)結(jié)構(gòu)體+鏈?zhǔn)角跋蛐窃?s時(shí)間內(nèi)穩(wěn)過 結(jié)構(gòu)體+靜態(tài)鏈表(上文代碼做法)可以卡常 其他一概過不了

3. 各種玄學(xué)問題

   比如用萬能頭就過了 但用普通頭過不了（不是說萬能頭慢嗎