CEOI2017Chase

HHHOJ#244 Park

题面传送门

我们开两个DP数组,分别表示从子树到点,放了次磁铁和从点到子树内某点,放了次磁铁的最大差异值。

同时考虑一条路径上的差异值贡献,推下式子可知是路径上点相连的所有点的权值和减去路径的权值(视DP方程情况而定)。

然后我们一边DFS一边用已知的更新未知的,当然还有反着做一遍。