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