Back to Leetcode

Readme

Binary_Search/3553.Minimum-Weighted-Subgraph-With-the-Required-Paths-II/Readme.md

latest828 B
Original Source

3553.Minimum-Weighted-Subgraph-With-the-Required-Paths-II

本题的第一个知识点是:在一棵树里,联通u,v,w三个节点的最小子树的权重和,就是[dist(u,v)+dist(u,w)+dist(v,w)]/2.

本体的第二个知识点是:在一棵树里,联通x,y两点的路径长度,等于dist(r,x)+dist(r,y)-2*dist(r,c),其中r是整棵树的根节点,c是x和y的LCA(lowest common ancester)。

任意一点到距离根节点的距离dist(r,x)可以通过DFS得到。于是本题的关键点就是求任意两点的LCA,于是就是一个binary list经典题。

我们需要处理得到一个数组up[v][k],表示节点v往上(朝根节点方向)走2^k步能够得到的位置。转移方程就是up[v][k] = up[up[v][k-1]][k-1]. 边界条件就是对于一对父子节点a->b,有up[b][0]=a.