换根dp
背景
标签:换根,搜索,答案,节点,我们,dp From: https://www.cnblogs.com/hyf-9134/p/18141002对于一颗无根树而言,假如我们有着把每个节点当成根节点的需求时,那么原先的直接从根节点开始搜索就无法满足我们的时间效率
此时我们就需要考虑转换策略研究,有没有什么好的方法能够不去把每个节点当成根节点都跑一次搜索
考虑我们手中已有的信息,我们知道跑一次搜索能得到一个根节点(u)所要的答案,那么我们就想着能不能试着通过这个答案去得到其他节点为根节点时的答案
首先我们将考虑的其他节点理解为和u关系好的节点