爱奇艺 前端实习面经

题目：给你一颗树，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）= 53-1， 3-2， 3-4， 3-5 = 1 + 1 + 1 + 2 = 5例如：从 3 -> 4 时，5 + （5 - 2...