题解：P11379 [GESP202412 八级] 树上移动

· · 题解

前言

我可能是为数不多的初三还在打这个的蒟蒻了吧。

思路

一眼树上动规，GESP 真的很爱考树上问题、黑白点、小杨。

首先一个状态就是以当前节点为根节点的子树中最长的满足条件的路径数。

考虑如何更新这个状态，发现只存在两种情况：某一棵子树内的答案，以及两棵子树的最长向上连接到当前节点的链的长度之和加一。

情况一不用解释，关于情况二，其实就是找出一条最长的、经过根节点的且进入两棵子树的链。

然后考虑还有一种特殊情况，也就是一条子树向上的最长链的长度加一。也就是以当前节点为一个端点的一条链。

到这里就自然想到第二个状态：以当前节点为一个端点的当前子树内最长满足条件的链的长度。

然后我们发现“满足条件”是个很宽泛的性质，不太好解决，发现 k\le 1000，于是考虑状态加一维，表示经过 j 个黑色点的答案。

这样状态更新的复杂度会多出一个 k，但显然复杂度很对。你也可以加一些优化，像前缀和或者判断当前子树内总共的黑色节点数之类。

这样就完成了。

我认为动态规划类问题着重的是思想，并且这道题实现简单，所以代码是不必要的。以及太懒了。