bzoj1103

dfs序

dfs序真神奇

dfs求出入棧時刻和出棧時刻，然後在in和out分别打上1和-1就能統計路徑和了。

其實這裡dfs序能夠讓我們求一個點處于哪些節點的子樹内，而一個節點隻處于從自己到跟路徑的節點的。

這裡的dfs序有些像括号序列，如果一個點不在另一個點的子樹内，那麼也就不在另一個點的括号内，那麼另一個點的括号也閉合了，+1-1抵消

View Code