洛谷1600 天天愛跑步 (樹上差分)

轉換思路，枚舉每個觀察員，統計有哪些運動員會給觀察員做貢獻。因為給觀察員做貢獻的運動員都在觀察員的子樹内，是以 \(dfs\) 統計即可。對于一條運動員路徑，可以拆成從出發結點 \(u\) 到 \(lca\) 的路徑和從 \(lca\) 的終點 \(v\) 的路徑。

其中處在上行路徑上的觀察員 \(P\)，如果能觀察到這個運動員，那麼要滿足

\[dep[P]+w[P] = dep[u] \]

下行路徑上觀察員要觀察到該運動員要滿足

\[w[P]-dep[P]=dis(u,v)-dep[v] \]

開一個桶，每個觀察員分别對應一個桶中元素。在 \(dfs\) 枚舉觀察員時，同時統計目前節點作為運動員會對哪些觀察員産生貢獻，在桶中對應元素加上即可。統計完目前觀察員，還要減去多餘的貢獻。