算是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]]
然后是这道题中的一些细节部分,结合代码理解