20250714-飞鹰班夏令营-总结

### LCA

##### 练习一：

给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。

###### 思路：

直接用倍增法求LCA即可

##### 练习二：

给定一棵树，有 $q$ 个询问，问树上点 $a$ 到点 $b$ 的最短路径和点 $c$ 到点 $d$ 的最短路径是否会经过至少一个相同的节点

###### 思路：

先求出点 $a$ 和点 $b$、点 $c$ 和点 $d$ 的LCA，不妨设 $x=$ LCA$(a,b)$，$y=$ LCA$(c,d)$，且 $x$ 的深度比 $y$ 要大，由于$x$ 的深度比 $y$ 要大，所以不存在 $c$ 到 $d$ 的最短路径会与 $a$ 和 $b$ 的最短路径重合且不经过 $x$ 的情况，而又因为两点的LCA必定在两点的最短路径上，所以如果 $x$ 在 $y$ 到 $c$ 或 $y$ 到 $d$ 的链上，那么点 $a$ 到点 $b$ 的最短路径和点 $c$ 到点 $d$ 的最短路径一定会重合，那么对此进行判断即可

##### 练习三：

给定一棵树和树上任意三点，求距离三点距离之和最短的点

###### 思路：

求出三点中任意两点的LCA，并选取其中深度最大的点作为最终答案，通过分类讨论可以证明：
设三点分别为 $a,b,c$，且 $depth[a]≥depth[b]≥depth[c]$，其中 $depth[x]$ 表示节点 $x$ 的深度
当 $a,b,c$ 三点都处于一条链上时，显然去点 $b$ 也就是LCA$(b,c)$ 更优
当 $a,b$ 两点处于一棵子树，点$c$ 处于另外一棵子树时，显然去点 $b$ 也就是LCA$(a,b)$ 更优
当 $a,b,c$ 三点分别处于三棵子树时，LCA$(a,b)$$=$LCA$(b,c)$$=$LCA$(a,c)$，只有一个答案，故应去三点共同的LCA

### 二项式系数

##### 计算系数：

给定一个多项式 $(ax+by)^k$，求此二项式展开式中 $x^n+y^m$ 项的系数（$n+m=k$)

###### 思路：

通过二项式定理可得，若 $a=1,b=1$ 则 $x^n+y^m$ 的系数为 $C^n_k $ 即 $C^{k-n}_k$ 即 $C^m_k$，计算时取 $n,m$ 中较小的计算即可，当 $a≠1$ 且/或 $b≠1$ 时，在原本的系数基础上乘上 $a^n×b^m$ 即可

正在渲染内容...