礼物 换根dp 题目大意 有一棵n( n≤1e6n \leq 1e6n≤1e6 )个节点的树 , 要求找到一个根使得下面等式最大 . ∑i=1n∑j=1nLCS(i,j)\sum_{i=1}^{n}\sum_{j=1}^{n}LCS(i,j)i=1∑nj=1∑nLCS(i,j) 解题思路 换根DP , 因为每次我们都可以考虑把子节点换成根节点 , 转移是比较方便的 . 首先我们先找一个点作为根节点算出贡献 . 为了避免重复计算带来的麻烦 , 我先计算 i<ji<ji<j 的情况 , 最后乘上2再加上 i=ji = ji=j 的情况 . 当然其他方法也可以 , 只要考虑相关...