天天恨跑步,,,

· · 个人记录

本来是非常简单非常板子的题。。没想出来。希望是因为感冒的原因。。。

考虑某条链的情况,那么实际就是数距离某个点距离为 k 的前后两个位置所有的点数。

考虑树上其实是一样的。某个点 x 上头的答案,就是满足 u 是起点或者终点,使得 ux 的长度为 w_x,同时 u 到另一个端点的路径必须包含 x

考虑既然经过了 u,那么要么是起点在 u 子树内,要么是终点。两种情况的贡献式都好推。这时候我们发现样例一都过不了,因为重了。什么情况会重?起点和终点都在 x 的子树内,但是由于路径并不经过 x,或者是恰好对称,在 x 处算了两次。这时候可以差分掉。对两个贡献,在 LCA 上减去一个,LCA 父亲上再减去一个,就好了。操你妈的我是超级无敌大唐氏。