P2986 (USACO10MAR) Great Cow Gathering G 发表于 2021-02-06 更新于 2023-08-02 分类于 oi , 总结 , dp 换根 dp 模板题 设 f(x,d)f(x,d)f(x,d) 表示在 x 的子树中,与 x 距离为 d 的点值之和。 设 g(x,d)g(x,d)g(x,d) 表示与 x 相距 d 的点之和 g(x,d)=f(x,d)+g(fa,d−1)−f(x,d−2)g(x,d)=f(x,d)+g(fa,d-1)-f(x,d-2) g(x,d)=f(x,d)+g(fa,d−1)−f(x,d−2) 答案为 g 的前缀和