题目链接: https://www.luogu.org/problemnew/show/P3174
这应该是我第一次没看 sol 做紫题吧……
虽然个人感觉比大多数紫题简单许多
题目本质是要求最长链的，但是要求是带每个点周围点的
我们设每个点的点权是这个点的连接点个数减 1
然后求最长链
得出来的链的长度 +2 即为答案
可以理解为因为大多数点都有一条边要连出去防止重复计算而减一
但是这样链头链尾会没算上，所以加二
Continue reading “Luogu P3174 [HAOI2009]毛毛虫”