240331米哈游笔试第三题

题目：给你一颗树，n个节点，边长为1，求任意两点的路径和。u, v 和 v, u 算同一条路径，故只算一次。（已经简化了，本来是还有一些边长为0，可以把0的点缩掉）

先以节点1为起点，计算1到各个点的路径和。

1-3, 1-2, 1-4, 1-5 = 8

然后换根，进行dfs，向子树移动

移动到 3 节点时，增量 = - (目标子树 - 1) + (n - 目标子树 - 1) = n - 2 * 目标子树

例如：从 1 -> 3 时，8 + （5 - 4 * 2）= 5

3-1， 3-2， 3-4， 3-5 = 1 + 1 + 1 + 2 = 5

例如：从 3 -> 4 时，5 + （5 - 2 * 2）= 6

4-1， 4-2， 4-3， 4-5 = 2 + 2 + 1 + 1 = 6

例如：从 3 -> 2 时，5 + （5 - 1 * 2）= 8

例如：从 4 -> 5 时，6 + （5 - 1 * 2）= 9

最终，每条边被计算两次，所以最终答案/2

result = (8 + 5 + 6 + 8 + 9) / 2 =18