洛谷P1600 [NOIP2016 提高組] 天天愛跑步
一、大緻分析
資料範圍中有提示樹可能退化為一條鍊，是以模拟時間複雜度可以達到\(O(nm)\)，顯然過不了。
繼續分析題目，可以發現對于一條從\(s_i\)到\(t_i\)的路徑可以\(s_i\)與\(t_i\)的最近公共祖先\(lca_i\)分為兩段對于其上某點符合要求的\(k\)，有：
若\(k\)在上行段，則\(deep_k + w_k = deep_{s_i}\)
若\(k\)在下行段，則\(dist_{{s_i},{t_i}} - w_k = deep_{t_i} - deep_k\)，即\(dist_{{s_i},{t_i}} - deep_{t_i} = w_k - deep_k\)
除了以上兩個式子外，又注意到能對\(k\)産生貢獻的路徑其起點及終點必然在以\(k\)為根的子樹上，是以可以開兩個數組，并在深度優先周遊時以上式左側的方式記錄，并以右式的方式統計。
但此處需要注意，\(k\)被經過的次數并不是向下遞歸直接通過數組查詢，而是遞歸完子樹後的值與進入子樹之前的值之差。
二、代碼&一些細節
普通的讀入，不專門放代碼了。
比較模版的樹剖求LCA （不想開二維數組寫倍增，其他的不會），不解釋了。
\(dist_i\)：第i條路徑的長度
\(st_i\)：以i為起點的路徑的數量
\(add1\)：以鍊式前向星存儲以i為開頭的路徑的集合
\(add2\)：以鍊式前向星存儲以i為起點及終點的最近公共祖先的路徑的集合
需要注意的是，若路徑的起點或終點與LCA重合，且此處符合要求，則會被統計兩次，是以提前減去。
<code>if (dep[lca] + w[lca] == dep[s[i]]) ans[lca]--;</code>
\(bu1\)：用以存儲上行段的貢獻
\(bu2\)：用以存儲下行段的貢獻，\(dist_{{s_i},{t_i}} - deep_{t_i}\)可能小于\(0\)，故加上\(MAXN\)。
沒什麼可說。