[TOC]
换根DP
这种算法的本质是什么？
答：以图中的这棵树为例，从「以 0 为根」换到「以 2 为根」时，原来 2 的子节点还是 2 的子节点，原来 1 的子节点还是 1 的子节点，唯一改变的是 0 和 2 的父子关系。由此可见，一对节点的距离的「变化量」应该是很小的，那么找出「变化量」的规律，就可以基于 ans[0] 算出 ans[2] 了。这种算法叫做换根 DP。
题单
- 310. 最小高度树（做法不止一种）
- 2581. 统计可能的树根数目
- Codeforces 771C. Bear and Tree Jumps（本题进阶版）
