P1600:天天爱跑步题解

解法

翻译一下:

给你一棵带点权的树和一堆路径,问对于每一个点\(i\)有多少条路经满足\(w(s,i) = weight(i)\)。

听起来就挺毒瘤的,是吧。根据这一类树上问题的套路,考虑把所有路径拆成\((s \to LCA(s,t))\)和\((t \to LCA(s,t))\),分开处理。我们先来处理\((s \to LCA(s, t))\)这一类问题:假设我们现在要知道路径\((s \to LCA(s, t))\)对点\(i\)的贡献,必须满足:

Continue reading →