$70$分$dp$,
虽然原题是磁铁,我还是说面包屑吧
图稍小
$f_{x,i}$表示走到$x$为止用了$i$次,枚举起点进行转移
转移$f_{x,i}=max(f_{pre,i},f_{pre,i-1}+sz_{x})$,这里$sz$表示的是儿子的权值和,不包括当前点
为什么这样转移,考虑你在当前撒下面包屑那么走到任意一个儿子差值都是这些,
不考虑父亲,在当前撒下面包屑儿子节点鸽子被吸引过来,走到儿子节点旅行家遇到鸽子数量不变,小学生遇到鸽子比旅行家多的就是儿子权值和
为什么不考虑父亲,父亲的贡献被父亲的父亲考虑了,
原文：https://www.cnblogs.com/znsbc-13/p/11631879.html