NOIP 2016 天天愛跑步
洛谷傳送門
JDOJ傳送門
6 3 2 3 1 2 1 4 4 5 4 6 0 2 5 1 2 3 1 5 1 3 2 6
2 0 0 1 1 1
先口胡一下部分分。
首先1号、2号，隻有0時刻出現的觀察員能夠看到人，所有人都在0時刻出現。那麼樹上差分統計人數即可。
3号、4号，也是隻有0時刻觀察員，隻統計起點即可。
5号，暴力可過。
9-12号，由于起點固定，是以每個人跑到每個點的時間可以用性質算出來，然後按這個性質統計即可。
13-16号同理。
那麼再考慮正解。
9-12和13-16号點可以給我們很大的啟發：我們發現針對起點為1、終點為1的路徑，都是按性質走的，是以我們就可以得到一個啟發：将一條路徑拆分成兩個支路來解決。這樣的話，這樣的兩條之路可以分别利用性質來處理。
這個性質是：在上行路徑上，滿足
\[deep[s]-deep[x]=t[x]
\]
這樣的點是對答案有貢獻的。
在下行路徑上，滿足
\[deep[s]+deep[x]-2\times deep[lca]=t[x]
那麼對于每一個節點\(x\)，根據以上性質，就有\(deep[s]=deep[x]+t[x]\)，也就是說，對于一條起點為s的上行路徑來講，它會對這個路徑上所有滿足這個性質的點作貢獻。
下行路徑同理。
那麼怎麼處理呢？思路到這裡，權值線段樹的想法就比較自然了。按起始節點s的深度deep[s]來統計人數。是以我們可以考慮用權值線段樹（動态開點）來維護這個資訊。然後通過樹上差分快速處理新路徑。最後隻需要從下到上線段樹合并統計即可。
注意，上行和下行要統計兩遍。
代碼：