首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往
您找到你想要的搜索结果了吗?
是的
没有找到

面试算法题

树形 dp。一般两遍 dfs 就能解决。 第一遍 dfs 用 son[i] 记录每个节点多少个子孙,用 dis[i] 记录 i 点到其所有子孙的距离之和。 son[i]和 dis[i]都在回溯的过程进行维护。假设 v 是 u 的孩子节点,\(son[u]+=son[v]+1\), \(dis[u] += dis[v]+son[v]+1\),也就是说 v 的每个子孙到 u 的距离是他们到 v 的距离+1,然后再加上 v 到 u 的距离1。 第二遍 dfs,维护 dis[i] 为到所有点的距离之和。节点 v 到其它所有节点的距离之和可以用 u 到其它所有节点的距离之和计算出来。因为v和v 的子孙到 v 的距离要比到 u 的距离少1,就减去了son[v]+1,然后剩下 n-son[v]-1个点到 v 的距离要比到 u 的距离多1,就加上了 n-son[v]-1,所以就是 \(dis[u]+n-2\times son[v]-2\)。 手写代码,大概是下面这样。

01
领券