『树形DP·换根』Kamp

本文主要是介绍『树形DP·换根』Kamp，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

题解

这道题$O(n^2)$很简单，就是一个简单的有根树树形DP，即经过每一个特殊点的边权*2-根到某一个特殊点的最长链。

对于部分1，我们假设处理了$f[x]$,对于一条边$(x,y,v)$来说，在一般情况下有：$f[y]=f[x]$

• 若在以y为跟的情况下可以不到达x，也就是$size[y]=k$,那么我们可以减去边权。
• 如果这条边原来没有被累加过，也就是$size[y]=0$,我们可以加上边权。

对于以某一个为根的最长链来说，我们对于边 ( x , y , v ) (x,y,v)

这篇关于『树形DP·换根』Kamp的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---