首先,声明换根 DP 不是树形 DP,不要用树形 DP 的思路学换根 DP
引入
Luogu P3478算是一道经典的换根 DP 题。
不考虑任何优化,纯朴素做法怎么做?
我们以每一个点为根跑一遍 DFS,求答案即可,非常简单。
但是这样的时间复杂度是 $ O(n^2)$ 的,非常慢。
所以有了换根 DP
思路
其实大部分换根 DP 的思路都是一样的
首先,n 个点你不会求,1个点肯定会求吧
我们以1节点为根先求一遍,(样例)得到了下图
此时的答案是18
那么,我们如果把4作为根,也就是把4提起来,变成了这样