换根DP get！之前Hygebra巨佬跟我讲过一遍，当时听懂了可惜后来忘了。。。昨天问了Binary_Search_Tree一道动态点分治的弱化版被换根DP吊锤了。。。
这里引用一下树形dp换根里对换根DP的总结，个人认为非常清楚：
以下为引用
换根解决的是“不定根”的树形dp问题。该类题目的特点是：给定一个树形结构，需要以每个节点为根进行一系列统计。
方法为两次扫描来求解：
第一次扫描时，任选一个点为根，在“有根树”上执行一次树形dp，在回溯时，自底向上的状态转移。
第二次扫描时，从第一次选的根出发，对整根树执行一个dfs，在每次递归前进行自顶向下的转移，计算出换根后的解。
引用结束
换根DP能\(O(n)\)解决一些不带修的、对树上所有节点统计答案的问题。
例题：
原文：https://www.cnblogs.com/With-penguin/p/12735684.html