算是NOIP中比較麻煩的題了,看題解感覺處理的很巧妙
題意就不再贅述了，剛開始的想法是周遊枚舉每一條路徑，但是無論如何這樣做的複雜度最壞都有O(nm)
是以嘗試換一種方法,從觀察員下手,對于每一個觀察員,我們隻需要找到每一條路徑帶給他的貢獻
那這個貢獻怎麼求呢?
對于每一條路徑(u,v),我們都可以将它拆為 u->lca 與 lca ->v
假設觀察員的位置p在 u-> lca 上,當depth[u]+w[p]=depth[p]時才會有貢獻
而當p在 lca->v 上時,隻有dist(u,v)-(depth[v]-depth[p])=w[p],即dist(u,v)-depth[v]=w[p]-depth[p]時才有貢獻
然後是統計貢獻,如果我們在統計貢獻時也一個一個去計算,那麼複雜度就又上去了,是以這個時候可以用一個桶來處理,
這也是這道題比較巧妙的一點,
先看u->lca,對于點x,我們将它貢獻的答案存在cnt[depth[x]]裡,對于這條路徑上的點p,更新答案就隻需要加上cnt[depth[p]+w[p]]
對于lca->v,我們就将答案貢獻存在cnt[dist(u,v)-depth[v]]裡,同理對于p,更新答案加上cnt[w[p]-depth[p]]
然後是這道題中的一些細節部分,結合代碼了解