# 圆锥曲线的蒙日圆

## 引子

对于椭圆，我们知道一个很经典的结论：

>过一点P能作椭圆两条垂直切线，则P轨迹在一个圆上，称该圆为这个椭圆的蒙日圆

听着是不是特别玄乎，下面让我们证明一下

## 椭圆的蒙日圆

已知椭圆方程为$\frac{x^2}{a^2}+\frac{y^2}{b^2}=1$，设$P(x_0,y_0)$，切线$y=k(x-x_0)+y_0$
$$
\begin{aligned}
&\begin{cases}
&y=kx-(kx_0-y_0)\\\\
&b^2x^2+a^2x^2-a^2b^2=0
\end{cases}
\\\\
&\Rightarrow 
(a^2k^2+b^2)x^2-2a^2k(kx_0-y_0)x+a^2(kx_0-y_0)^2-a^2b^2=0\\\\
&\Delta=4a^4k^2(kx_0-y_0)^2-4(a^2k^2+b^2)[a^2(kx_0-y_0)^2-a^2b^2]=0\\\\
&\Rightarrow 
a^4k^2(kx_0-y_0)^2-a^2(a^2k^2+b^2)(kx_0-y_0)^2+a^2b^2(a^2k^2+b^2)=0\\\\
&\Rightarrow 
-(kx_0-y_0)^2+a^2k^2+b^2=0\\\\
&\Rightarrow 
(a^2-x_0^2)k^2+2x_0y_0k-y_0^2+b^2=0\\\\
&\therefore k_1k_2=\frac{-y_0^2+b^2}{a^2-x_0^2}=-1\\\\
&\therefore x_0^2+y_0^2=a^2+b^2\\\\
&Q.E.D.
\end{aligned}
$$

## 抛物线的蒙日圆

常言道，抛物线就是一个被无限拉长的椭圆。那抛物线会不会也有“蒙日圆”呢？

不妨假设它有。既然抛物线是无限拉长的椭圆，那它的“蒙日圆”大概率就是一个被无限拉长的圆。无限拉长的圆？那不是一条直线吗？

下面来验证我们的猜想

已知抛物线$y^2=2px,P(x_0,y_0)$，设切线$x-x_0=m(y-y_0)$
$$
\begin{aligned}
&\begin{cases}
&y^2=2px\\\\
&x=my-my_0+x_0
\end{cases}\\\\
&y^2-2pmy+2p(my_0-x_0)=0\\\\
&\Delta=4p^2m^2-8p(my_0-x_0)=0\\\\
&\Rightarrow pm^2-2y_0m+2x_0=0\\\\
&\therefore m_1m_2=\frac{2x_0}{p}=-1\\\\
&\therefore x_0=-\frac{x_0}{2}
\end{aligned}
$$
故P的轨迹是抛物线准线，还真是一条直线！

## 双曲线

既然抛物线都能有，为什么双曲线不能有？

让我们做个更大胆的猜想

如果说抛物线是个拉长的椭圆，那你看这个双曲线。。。。。。

> 像不像个无限拉长并且绕回来的椭圆？

那它的“蒙日圆”？应该是套在中间的罢？

让我们来验证一下

已知双曲线$\frac{x^2}{a^2}-\frac{y^2}{b^2}=1,P(x_0,y_0)$，设切线$y-y_0=k(x-x_0)$
$$
\begin{aligned}
&\begin{cases}
&b^2x^2-a^2y^2-a^2b^2=0\\\\
&y=kx-kx_0+y_0
\end{cases}\\\\
&\Rightarrow 
(b^2-a^2k^2)x^2+2a^2k(kx_0-y_0)x-a^2(kx_0-y_0)^2-a^2b^2=0\\\\
&\Delta=4a^4k^2(kx_0-y_0)^2+4(b^2-a^2k^2)[a^2(kx_0-y_0)^2+a^2b^2]=0\\\\
&\Rightarrow a^2k^2(kx_0-y_0)^2+(b^2-a^2k^2)[(kx_0-y_0)^2+b^2]=0\\\\
&\Leftrightarrow 
b^2(kx_0-y_0)^2-a^2b^2k^2+b^4=0\\\\
&\Rightarrow (x_0^2-a^2)k^2-2x_0y_0k+y_0^2+b^2=0\\\\
&\therefore k_1k_2=\frac{y_0^2+b^2}{x_0^2-a^2}=-1\\\\
&\therefore x_0^2+y_0^2=a^2-b^2
\end{aligned}
$$
这不就夹在左右两支中间嘛！

## 小结

经过上述讨论，我们发现三种圆锥曲线都有其对应的“蒙日圆”。由此，圆锥曲线的统一性可见一斑！

圆锥曲线的蒙日圆

# 圆锥曲线垂直弦交点连线过定点

## 椭圆

### 命题描述

若直线$l$与椭圆$ C:\frac{x^2}{a^2}+\frac{y^2}{b^2}=1$交于A,B,两点,P$(x_0,y_0)\in C$,且$PA\perp PB$,则$l$过定点$\Big (\frac{a^2-b^2}{a^2+b^2}x_0,-\frac{a^2-b^2}{a^2+b^2}y_0\Big )$

### 证明

设$A(x_1,y_1)$ , $B(x_2,y_2)$ , $l:y=kx+m$

先看条件,有一个垂直,用上再说
$$
\because PA \perp PB
$$
$$
\therefore k_{PA}\cdot k_{PB}=-1 \Rightarrow \frac{y_0-y_1}{x_0-x_1}\cdot \frac{y_0-y_2}{x_0-x_2}=-1
$$

整理,得:
$$
x_0^2-(x_1+x_2)x_0+x_1x_2+y_0^2-(y_1+y_2)y_0+y_1y_2=0 \tag{1}
$$
按照惯例,联立$C,l$
$$
\begin{cases}
\frac{x^2}{a^2}+\frac{y^2}{b^2}=1\\\\
y=kx+b
\end{cases}
\Rightarrow (b^2+a^2k^2)x^2+2kma^2x+a^2(m^2-b^2)=0
$$
$$
\therefore x_1+x_2=-\frac{2kma^2}{b^2+a^2k^2},x_1x_2=\frac{a^2(m^2-b^2)}{b^2+a^2k^2}
$$
看看还漏了什么...还有一个$A,B$在$l$上没用

由$A,B\in l$
$$
\begin{cases}
y_1=kx_1+m\\\\
y_2=kx_2+m\\
\end{cases}
\therefore 
\begin{cases}
&y_1+y_2=k(x_1+x_2)+2m=\frac{2mb^2}{b^2+a^2k^2}\\\\
&y_1y_2=k^2x_1x_2+km(x_1+x_2)+m^2=\frac{b^2(m^2-a^2k^2)}{b^2+a^2k^2}
\end{cases}
$$
代入$(1)$得
$$
x_0^2+\frac{2kma^2}{b^2+a^2k^2}\cdot x_0+\frac{a^2(m^2-b^2)}{b^2+a^2k^2}+y_0^2-\frac{2mb^2}{b^2+a^2k^2}\cdot y_0+\frac{b^2(m^2-a^2k^2)}{b^2+a^2k^2}=0
$$
去分母,得
$$
(b^2+a^2k^2)(x_0^2+y_0^2)+(2kma^2)x_0+a^2(m^2-b^2)+b^2(m^2-a^2k^2)-2mb^2y_0=0
$$
~~展开之后有些项长的很像完全平方~~ 按完全平方整理,得 
$$
a^2(k^2x_0^2+2kmx_0+m^2)+b^2(m^2-2my_0+y_0^2)+b^2x_0^2-a^2b^2+a^2k^2y_0^2-a^2b^2k^2=0
$$
即
$$
a^2(kx_0+m)^2+b^2(y_0-m)^2+b^2x_0^2-a^2b^2+a^2k^2y_0^2-a^2b^2k^2=0 \tag{2}
$$
后面那一坨东西看着就恶心,能不能干掉呢?

这不还有一个$P$在$C$上没用嘛~

由$P \in C$
$$
b^2x_0^2+a^2y_0^2=a^2b^2
$$
故
$$
b^2x_0^2-a^2b^2+a^2k^2y_0^2-a^2b^2k^2=-a^2y_0^2+k^2(a^2y_0^2-a^2b^2)=-a^2y_0^2-b^2k^2x_0^2
$$
代入$(2)$,整理,得
$$
a^2[(kx_0+m)^2-y_0^2]=b^2[k^2x_0^2-(y_0-m)^2]
$$
这东西竟然是一个平方差!别急着约分,看看等不等于0先

$$\because P \notin l$$

$$\therefore kx_0+m-y_0 \neq 0$$

然后就可以开心地约分了!
$$
a^2(kx_0+m+y_0)=b^2(kx_0+y_0-m)
$$
故
$$
m=\frac{(b^2-a^2)(y_0+kx_0)}{a^2+b^2}
$$
故
$$
l: y=kx+\frac{(b^2-a^2)(y_0+kx_0)}{a^2+b^2}
$$
整理,得
$$
k\bigg [ x+\frac{(b^2-a^2)x_0}{a^2+b^2} \bigg ]=y-\frac{(b^2-a^2)y_0}{a^2-b^2}
$$
故$l$过定点:
$$
\bigg (\frac{a^2-b^2}{a^2+b^2}x_0,\frac{b^2-a^2}{a^2+b^2}y_0 \bigg )
$$
单独验证横线和竖线,符合上式 ~~其实是我懒得写~~

$$Q.E.D.$$

## 双曲线

### 命题描述

若直线$l$与双曲线$C: \frac{x^2}{a^2}-\frac{y^2}{b^2}=1$交于$A,B$两点,$P(x_0,y_0) \in C$且 $PB \perp PB$,则$l$过定点$\Big ( \frac{a^2+b^2}{a^2-b^2}x_0,-\frac{a^2+b^2}{a^2-b^2}y_0 \Big)$

### 证明

设$A(x_1,y_1),B(x_2,y_2),l:y=kx+m$

照例联立$C,l$
$$
\begin{cases}
b^2x^2-a^2y^2-a^2b^2=0\\\\
y=kx+m
\end{cases}
\Rightarrow (b^2-a^2k^2)x^2-2a^kmx-a^2b^2-a^2m^2=0
$$
$$
\therefore x_1+x_2=\frac{2a^2km}{b^2-a^2k^2},x_1x_2=\frac{-a^2b^2-a^2m^2}{b^2-a^2k^2}
$$



接下来就是垂直了,老是用斜率没意思,用一手向量点乘等于0

由$PA \perp PB$
$$
(x_0-x_1)(x_0-x_2)+(y_0-y_1)(y_0-y_2)=0
$$
由于$A,B$在$l$上,故
$$
\begin{aligned}
y_1=kx_1+m\\\\
y_2=kx_2+m
\end{aligned}
$$
故上式可化为
$$
(x_0-x_1)(x_0-x_2)+[(y_0-m)-kx_1][(y_0-m)-kx_2]=0
$$
即  
$$
x_0^2+(y_0-m)^2-\[x_0+k(y_0-m)\](x_1+x_2)+(k^2+1)x_1x_2=0
$$
代入韦达定理,得
$$
x_0^2+(y_0-m)^2-\frac{2a^2km[x_0+k(y_0-m)]}{b^2-a^2k^2}-\frac{(k^2+1)(a^2b^2+a^2m^2)}{b^2-a^2k^2}=0
$$
去分母,得
$$
(b^2-a^2k^2)x_0^2+(b^2-a^2k^2)(y_0-m)^2-2a^2km[x_0+k(y_0-m)]-(k^2+1)(a^2b^2+a^2m^2)=0
$$
隐隐约约看到写完全平方的影子,找出来写在一起:
$$
-a^2(k^2x_0^2+2kmx_0+m^2)+b^2x_0^2-a^2k^2[(y_0-m)^2+2m(y_0-m)+m^2]+b^2(y_0-m)^2-k^2a^2b^2-a^2b^2=0
$$
然后就可以化成平方啦,整体代入不展开真是个好习惯~
$$
-a^2(kx_0+m)^2+b^2x^2-a^2k^2y_0^2+b^2(y_0-m)^2-k^2a^2b^2-a^2b^2=0 \tag{1}
$$
由$P \in C$得:$b^2x_0^2-a^2y_0^2-a^2b^2=0$
故
$$
\begin{aligned}
-a^2y_0^2=a^2b^2-b^2x_0^2\\\\
-a^2b^2=a^2y_0^2-b^2x_0^2
\end{aligned}
$$
代入$(1)$,得
$$
\begin{aligned}
&-a^2(kx_0+m)^2+b^2x_0^2+k^2a^2b^2-k^2b^2x_0^2+b^2(y_0-m)^2-k^2a^2b^2+a^2y_0^2-b^2x_0^2=0\\\\
&\Leftrightarrow -a^2(kx_0+m)^2+b^2(y_0-m)^2-k^2b^2x_0^2+a^2y_0^2=0\\\\
&\Leftrightarrow a^2[y_0-(kx_0+m)^2]+b^2[(y_0-m)^2-k^2x_0^2]=0
\end{aligned}
$$
然后就来到了喜闻乐见的平方差环节
$$
a^2(y_0+kx_0+m)(y_0-kx_0-m)+b^2(y_0-m+kx_0)(y_0-m-kx_0)=0
$$
还是要按照惯例判断是否为零

$$\because P \notin C$$

$$\therefore y_0-kx_0-m \neq 0$$

然后就可以约分啦~
$$
a^2(y_0+kx_0+m)+b^2(y_0+kx_0-m)=0
$$

$$
\Rightarrow m=\frac{(a^2+b^2)y_0+(a^2+b^2)kx_0}{b^2-a^2}=-\frac{(a^2+b^2)(kx_0+y_0)}{a^2-b^2}
$$

故
$$
l: y=kx-\frac{(a^2+b^2)(kx_0+y_0)}{a^2-b^2}
$$
单独把$k$拎出来
$$
y+\frac{y_0(a^2+b^2)}{a^2-b^2}=k\bigg (x-\frac{x_0(a^2+b^2)}{a^2-b^2}\bigg )
$$
故$l$过定点:
$$
\bigg ( \frac{a^2+b^2}{a^2-b^2}x_0,-\frac{a^2+b^2}{a^2-b^2}y_0\bigg )
$$
单独验证横线和竖线,符合上式

$$Q.E.D.$$

## 抛物线

### 命题描述

若直线$l$与抛物线$C: y^2=2px$交于$A,B$两点,$P(x_0,y_0)\in C$,且$PA \perp PB$,则$l$过定点$(2p+x_0,-y_0)$

### 证明

~~整完双曲线以为抛物线有手就行,然鹅...这真是一个悲伤的故事...~~

设$A(x_1,y_1),B(x_2,y_2),l:x=my+n$

横抛物线肯定是这样设直线简单啦~

照例联立$C,l$
$$
\begin{cases}
y^2=2px\\\\
x=my+n
\end{cases}
\Rightarrow y^2=2pmy-2pn=0
$$
$$
\therefore y_1+y_2=2pm,y_1y_2=-2pn
$$
照例向量点乘等于0

$$\because PA \perp PB$$

$$\therefore (y_0-y_1)(y_0-y_2)+(x_0-x_1)(x_0-x_2)=0$$

由于$A,B$在$l$上
$$
\begin{aligned}
x_1=my_1+n\\\\
x_2=my_2+n
\end{aligned}
$$
代入上式,得  
$$
y_0^2+(x_0-n)^2-\[y_0+m(x_0-n)\](y_1+y_2)+(m^2+1)y_1y_2=0
$$
代入韦达定理,得
$$
\begin{aligned}
&y_0^2+(x_0-n)^2-2pm[y_0+m(x_0-n)]-2pm^2n-2pn=0\\\\
&\Leftrightarrow y_0^2-2pmy_0+(x_0-n)^2-2pm^2x_0-2pn=0
\end{aligned}
$$
$$\because P \in C$$

$$\therefore y_0^2=2px_0$$

代入上式,然后是一通十分Genius的操作,注意,核心所在! ~~我是怎么想出来的?~~

$$
\begin{aligned}
&y_0^2-2pmy_0+(x_0-n)^2-m^2y_0-2pn=0\\\\
&\Leftrightarrow (1-m^2)y_0^2-2pmy_0+(x_0-n)^2-2pn=0\\\\
&\Leftrightarrow (1-m^2)y_0^2-2pmy_0-p^2+(x_0-n)^2-2pn+p^2=0 \leftarrow 妙不可言!\\\\
&\Leftrightarrow [(1+m)y_0+p][(1-m)y_0-p]+(x-n+p)^2-2px_0=0\\\\
&\Leftrightarrow (y_0+my_0+p)(y_0-my_0-p)+(x_0-n+p)^2-y_0^2=0\\\\
&\Leftrightarrow y_0^2-(my_0+p)^2+(x_0-n+p)^2-y_0^2=0\\\\
&\Leftrightarrow (x_0-m+p)^2-(my_0+p)^2=0
\end{aligned}
$$
然后就又到了喜闻乐见的平方差环节
$$
(x_0-n+p+my_0+p)(x_0-n+p-my_0-p)=0
$$
即
$$
(x_0-n+my_0+2p)(x_0-n-my_0)=0
$$
剩下的就是常规操作啦

$$\because P \notin C$$

$$\therefore x_0-n-my_0 \neq 0$$

故
$$
\begin{aligned}
x_0-n+my_0+2p=0\\\\
\Rightarrow n=my_0+x_0+2p
\end{aligned}
$$
然后就可以愉快地写出直线的方程
$$
l: x=my+my_0+x_0+2p
$$
还是把$m$单独拿出来
$$
x-(x_0+2p)=m(y+y_0)
$$
故$l$过定点:
$$
(x_0+2p,-y_0)
$$
单独验证横线和竖线,符合上式

$$Q.E.D.$$

## 花絮

看到这里,你一定很好奇我到底算了多久吧?你一定很好奇我是怎么想到做法的吧?不如来看看这4大张草稿纸吧(笑~)

![椭圆草稿纸](https://s3.ax1x.com/2021/02/27/69iew8.jpg)

![双曲线草稿纸](https://s3.ax1x.com/2021/02/27/69iEOP.jpg)

![抛物线草稿纸,附送大问号一枚](https://s3.ax1x.com/2021/02/27/69iAyt.jpg)

![太激动了又验算了一遍](https://s3.ax1x.com/2021/02/27/69iZef.jpg)

## 参考资料

椭圆证明来自:[爱数学的筑梦人:曲线上定点引垂直弦，交点连线过定点](https://mp.weixin.qq.com/s/Xy4Sas2ayUKQKZZtBHRxoA)

封面图:[知乎:【解析几何】什么是极线，好吃吗?](https://zhuanlan.zhihu.com/p/33873965)

圆锥曲线垂直弦交点连线过定点

# deepin20编译安装dde-top-panel

## 依赖

libqt5widgets5 libqt5concurrent5 libqt5x11extras5-dev libqt5svg5-dev libdtkwidget-dev libkf5windowsystem-dev libdframeworkdbus-dev libdtkgui-dev cmake libdtkcore-bin  g++ libxdo-dev libdtkcore5-bin libxcb-ewmh-dev libgsettings-qt-dev qt5-default

## 下载文件

[下载dde-top-panel的源代码和release](https://github.com/SeptemberHX/dde-top-panel)

[下载全局菜单的release](https://github.com/SeptemberHX/dde-globalmenu-service.git)

## 编译

顶栏高度的配置在/dde-top-panel-master/frame/util/CustomSettings.cpp的25行

进入dde-top-panel目录，执行：

```shell
mkdir build
cd build
cmake ..
make
```

注意，源码的路径里不能有中文！

编译出的文件会在：build/frame/dde-top-panel

## 安装dde-top-panel

1. 将com.deepin.dde.toppanel.gschema.xml 复制到/usr/share/glib-2.0/schemas

2. 执行

   ```shell
   sudo glib-compile-schemas /usr/share/glib-2.0/schemas
   ```

3. 赋予dde-top-panel可执行权限：

   ```shell
   chmod +x dde-top-panel
   ```

4. 将dde-top-panel复制到你喜欢的目录（比如/opt），记下路径

5. 新建一个文本文档，输入以下内容：

   >[Desktop Entry]
   >Comment=DDE Top Panel
   >Exec=/opt/dde-top-panel
   >Hidden=false
   >Name=dde-top-panel
   >Type=Application
   >X-Deepin-Vendor=user-custom
   >X-GNOME-Autostart-enabled=true

   其中的“Exec=”后面的内容替换为dde-top-panel可执行文件的路径，要写完整路径！

6. 将这个文件的扩展名由.txt改为.desktop

7. 将这个文件复制到~/.config/autostart

8. 注销或重启或者直接双击运行

## 启用全局菜单

1. 赋予dde-globalmenu-service可执行权限
2. 复制 dde-globalmenu-service 到 /usr/bin
3. 复制 dde-globalmenu-service.desktop 到 ~/.config/autostart
4. 修改文件 ~/.gtkrc-2.0 ，添加 gtk-modules=appmenu-gtk-module
5. 修改文件 ～/.config/gtk-3.0/settings.ini ，[Settings] 条目下 添加 gtk-modules=appmenu-gtk-module
6. apt 安装 appmenu-qt appmenu-gtk2-module appmenu-gtk3-module  libdbusmenu-gtk3-4  libdbusmenu-gtk4 libdbusmenu-qt5-2 
7. 注销或重启

## 去除最大化窗口时的标题栏

在 ~/.config/kwinrc 添加配置：
[Windows]
BorderlessMaximizedWindows=true
然后重新登录

## 插件

将插件复制到 ~/.local/lib/dde-top-panel/plugins 下

### de-istate-menus

[下载release](https://github.com/SeptemberHX/dde-istate-menus)

3.0版本只兼容部分英特尔cpu，如果崩溃，请使用2.0版本

>需要安装新依赖：libsensors5
>确保执行过 sensors-detect，且 sensors 有输出。
>需要重新设置权限
>功耗只支持部分 Intel CPU，由于Linux上没有获取功耗的统一接口，导致该部分功能直接和硬件挂钩，很容易不兼容然后导致 top-panel 闪退。如有问题，请暂时使用 0.2 版本

#### 安装依赖

```shell
sudo apt install libqt5charts5
```

#### 给予权限

```shell
sudo setcap cap_net_raw,cap_dac_read_search,cap_sys_ptrace+ep <dde-top-panel的路径>
```

#### 安装

将插件复制到~/.local/lib/dde-top-panel/plugins即可

## 参考资料

[septemberhx:dde-top-panel](https://bbs.deepin.org/zh/post/195128)

[septemberhx:dde-istate-menus](https://bbs.deepin.org/zh/post/195858)

[github:dde-top-panel](https://github.com/SeptemberHX/dde-top-panel)

deepin20编译安装dde-top-panel

# 倍增LCA
## 引子
什么？你还不知道什么是LCA？LCA就是树上两个节点的最近公共祖先。  
所以，对于怎么找LCA，是个人都会想到一个办法，让两个节点不断向上移动，只要重合了就是LCA了，嘿嘿嘿  
然鹅，一个一个移动太慢，只要数据过了 $10^8$ 分分钟 T 飞~  
所以，我们需要一个快速的移动方式，比如，成几何级数的移动，这就是倍增算法  

## 基本思路  
既然要成几何级数的移动速度，要找个底数，比如2吧，每次移动 $2^k$ 个  
要想一次移动这么多，肯定要预处理，不如先预处理一个数组 $grand[i][j]$ 表示 $i$ 向上跳$$2^k$$个是谁，跳出这棵树的值就为-1吧  
怎么判断已经跳到了LCA呢？毕竟公共祖先不只有LCA一个  
不如就不直接跳到LCA，把所有跳到相同节点的情况都视为跳出树了，一直跳直到跳不动了为止，这时候两个节点的父节点就是LCA了，是不是特别机智~  

## 预处理

怎么预处理出 $grand$数组呢？
什么？你想一个个往上跳，然后取对数？省省吧，有这功夫早就 T 飞了，我们需要一个更高效的方法，最好能利用已经求出的 $grand$ 数组  
那不就是动态规划嘛，让我们来凑一手状态转移方程  
首先，$i$ 向上跳 $2^k$ 个可以分解成两个动作，先向上跳 $2^{k-1}$ 个，再向上跳 $2^{k-1}$ 个  
$i$向上跳 $2^{k-1}$ 个不就是$grand[i][k-1]$嘛，套个娃，再向上跳 $2^{k-1}$ 个当然就是 $grand[grand[i][k-1]][k-1]$ 。于是我们得出方程：
$$
grand[i][k]=grand[grand[i][k-1]][k-1]
$$
瞅瞅这个方程，我们该用什么算法呢？  
要想转移状态，必须要先求出 $grand[i][k-1]$，这告诉我们应该：
```cpp
for(int k=;k< MAXON;k++)
{
  //求grand
}
```
再看，我们还要先求出$i$的祖先节点的$grand$，因为我们要用到$grand[grand[i][k-1]][k-1]$ 嘛，这好说，来一手 $dfs$ 深度优先搜索就好了，顺便还可以记录每个节点的父节点和深度，一举两得    
于是我们竟然可以写出代码了
先用邻接表存图：
```cpp
	struct edge
	{
		int to;//这条边到达的点
		int next;//下一条边
	}Edge[MAXON];
	int head[MAXON];//head[i]表示由i开始的第一条边的编号
	int tot=0;//总边数
	int grand[500010][30];
	int fa[MAXON];
	void add_dege(int from, int to)
	{
		tot++;//当前边的编号
		Edge[tot].to = to;
		if (from != -1)
			Edge[tot].next = head[from];//插入在前
		head[from] = tot;//由于这条边插入在了前面,故当前边就是由from开始的第一条边
	}
```
```cpp
void dfs(int from, int now)
	{
		fa[now] = from;//记录父节点
		int start = head[now];//从第一个子节点开始找
		if (from != -1)//若不是根节点,深度为父节点深度+1(根节点为0)
			dep[now] = dep[from] + 1;
		//int g = log2(dep[now]) ;
		int g = lg[dep[now]];
		if (from != -1)//根节点没有父节点
			grand[now][0] = from;//2^0=1,即父节点
		for (int i = 1; i < = g; i++)
		{
			grand[now][i] = grand[grand[now][i - 1]][i - 1];//状态转移方程
		}
		while (start)//一个一个找孩子
		{
			if (Edge[start].to == from)//若相连节点不是父节点
			{
				start = Edge[start].next;
				continue;
			}
			dfs(now, Edge[start].to);//继续搜索子节点
			start = Edge[start].next;//搜索下一个子节点
		}
	}
```

## 跳！
预处理好了，接下来就是跳了  
怎么跳呢？先跳到同一高度，然后什么都好说
```cpp
		if (dep[a] > dep[b])//统一b深度大于a
		{
			a = a + b;//a此时等于原来的a,b之和
			b = a - b;//b此时等于原来的a
			a = a - b;//a此时等于原来的b
		}//神奇的交换方法
		int deep = dep[b] - dep[a];//深度差
		//int step = log2(deep);
		int step = lg[deep];//最大要走的步数
		for (int i = step; i >= 0; i--)//先让b跳到和a同一深度
		{
			if (dep[grand[b][i]] < dep[a]) continue;//跳过头了,不跳
			else
			{
				b = grand[b][i];//没跳过头,跳
			}
		}
		if (a == b) return a;//若相等,则已经找到LCA
```
这里为什么要有个step呢，因为先封个顶，一点点下降，能跳再跳，万一就跳出去了呢  
然后就是两个节点一起向上跳了
```cpp
		step = lg[dep[a]]; //要走的步数
		//step = log2(dep[a]);
		for (int i = step; i >= 0; i--)
		{
			if (grand[a][i] == grand[b][i]) continue;//跳过头了,不跳
			else//没跳过头,跳
			{
				a = grand[a][i];
				b = grand[b][i];
			}
		}
		return fa[a];//最后他们的父节点就是LC
```
要问这个$lg$数组是怎么来的？洛谷上抄的，嘿嘿嘿
```cpp
	for (int i = 1; i < = n; i++) //常数优化,预先算出log_2(i)+1的值，用的时候直接调用就可以了
		lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);  //看不懂的可以手推一下
```

## 完整代码
我写这玩意的时候特别喜欢class，于是。。。码风奇丑，凑合着看吧。。。
```cpp
#include<cmath>
#include<cstdio>
#include<iostream>
using namespace std;
const int MAXON = 1000010;
int dep[MAXON];//dep[i]代表编号为i的点所处的深度
int lg[MAXON];
class Graph
{
private:
	struct edge
	{
		int to;//这条边到达的点
		int next;//下一条边
	}Edge[MAXON];
	int head[MAXON];//head[i]表示由i开始的第一条边的编号
	int tot;//总边数
	int grand[500010][30];
	int fa[MAXON];
public:
	Graph()
	{
		tot = 0;
	}
	void add_dege(int from, int to)
	{
		tot++;//当前边的编号
		Edge[tot].to = to;
		if (from != -1)
			Edge[tot].next = head[from];//插入在前
		head[from] = tot;//由于这条边插入在了前面,故当前边就是由from开始的第一条边
	}
	void dfs(int from, int now)
	{
		fa[now] = from;//记录父节点
		int start = head[now];//从第一个子节点开始找
		if (from != -1)//若不是根节点,深度为父节点深度+1(根节点为0)
			dep[now] = dep[from] + 1;
		//int g = log2(dep[now]) ;
		int g = lg[dep[now]];
		if (from != -1)//根节点没有父节点
			grand[now][0] = from;//2^0=1,即父节点
		for (int i = 1; i <= g; i++)
		{
			grand[now][i] = grand[grand[now][i - 1]][i - 1];//状态转移方程
		}
		while (start)//一个一个找孩子
		{
			if (Edge[start].to == from)//若相连节点不是父节点
			{
				start = Edge[start].next;
				continue;
			}
			dfs(now, Edge[start].to);//继续搜索子节点
			start = Edge[start].next;//搜索下一个子节点
		}
	}
	int lca(int a, int b)
	{
		if (dep[a] > dep[b])//统一b深度大于a
		{
			a = a + b;//a此时等于原来的a,b之和
			b = a - b;//b此时等于原来的a
			a = a - b;//a此时等于原来的b
		}//神奇的交换方法
		int deep = dep[b] - dep[a];//深度差
		//int step = log2(deep);
		int step = lg[deep];//最大要走的步数
		for (int i = step; i >= 0; i--)//先让b跳到和a同一深度
		{
			if (dep[grand[b][i]] < dep[a]) continue;//跳过头了,不跳
			else
			{
				b = grand[b][i];//没跳过头,跳
			}
		}
		if (a == b) return a;//若相等,则已经找到LCA
		step = lg[dep[a]]; //要走的步数
		//step = log2(dep[a]);
		for (int i = step; i >= 0; i--)
		{
			if (grand[a][i] == grand[b][i]) continue;//跳过头了,不跳
			else//没跳过头,跳
			{
				a = grand[a][i];
				b = grand[b][i];
			}
		}
		return fa[a];//最后他们的父节点就是LCA
	}
};
Graph G;
int main()
{
	int n, m, s;
	//cin >> n >> m >> s;
	scanf("%d%d%d", &n, &m, &s);
	for (int i = 1; i <= n; i++) //常熟优化,预先算出log_2(i)+1的值，用的时候直接调用就可以了
		lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);  //看不懂的可以手推一下
	n--;
	while (n--)
	{
		int a, b;
		//cin >> a >> b;
		scanf("%d%d", &a, &b);
		G.add_dege(a, b);
		G.add_dege(b, a);
	}
	G.dfs(-1, s);
	while (m--)
	{
		int a, b;
		//cin >> a >> b;
		scanf("%d%d", &a, &b);
		int ans = G.lca(a, b);
		if (ans == -1)
			printf("%d\n", s);
		//cout << s << endl;
		else
			printf("%d\n", ans);
		//cout << ans << endl;
	}
	return 0;
}
```


倍增LCA

# 简介
主席树是一种数据结构，用来解决区间第k小(大)问题。要问为什么叫主席树？因为这是一个叫黄嘉泰的dalao发明的 ~~名字缩写跟我国某位主席一样，Orz~~  
时间复杂度是Onlogn，十分优秀 ~~空间复杂度倒是有点大~~  
# 前置姿势
## 权值线段树
+ 众所周知，权值线段树是一种线段树 ~~话说这不是废话吗2333~~
+ 它不同于一般线段树的是它的每一个结点的值代表这个区间中的数在序列中出现的总次数，正所谓“权值”
+ 它可以被用来处理区间第k小(大)问题

### 查询原理
此处利用二分的思想：
现有区间[l,r],不妨设区间[l,m] ( m为区间中间位置 ) 内的数的个数为n: 
显然:  
若 n < k ，第k小就是区间[m+1,r]的第 k - n 小
反之，则为区间[l,r]的第k小
于是可以写出伪代码
```cpp
int que(k,l,r)//询问区间[l,r]的第k小
{
    if(l==r) return l;
    int m=(l+r)/2;
    if(cnt(l,m)>=k) return que(k,l,m);
    return que(k-cnt(l,r),m+1,r);
}
```
#### 举个栗子
对于序列 1,3,2,2,0,1 建立的权值线段树如下
![](https://s1.ax1x.com/2020/06/02/tt4T3R.png)  
查询第3小：  
1. 访问区间[0,3],有6个数，> 3
2. 访问左区间[0,1]查询第3小,有3个数,=3
3. 访问右区间[1,1],查询第2小，返回结果->1

### 建树
当然是递归建树啦ψ(｀∇´)ψ  
此处同普通线段树,只需统计区间个数即可  
此处使用暴力统计 ~~其实是懒得打~~  
```cpp
int ls[100],rs[100],cnt=0,v[100];
int l[100],r[100];
int num[100];
int n;
void update(int p)
{
    v[p]=v[ls[p]]+v[rs[p]];
}
void build(int p,int l,int r)
{
    l[p]=l;r[p]=r;
    if(l==r)
    {
        for(int i=0;i<n;i++)
        {
            if(num[i]>=l&&num[i]<=r) v[p]++;
        }
        return;
    }
    int m=l+r>>1;
    ls[p]=++cnt;
    rs[p]=++cnt;
    build(ls[p],l,m);
    build(rs[p],m+1,r);
    update(p);
}
```
### 查询
```cpp
int que(int p,int k)
{
    if(l[p]==r[p]) return l;
    int m=l[p]+r[p]>>1;
    if(v[p]<k) return que(rs[p],k-v[p]);
    return que(ls[p],k);
}
```
# 思想
权值线段树有一个缺点，只能查询整个区间的第k小，对于子区间就无能为力了  
那是不是对于所有子区间都能搞出一个权值线段树就好了呢？  
## 前缀和
这里就可以用前缀和的思想：  
若用相同范围（即相同的l，r）对任意子区间建树，所有的权值线段树结构相同，这意味着两棵树可以相减（即每一个等位节点相减）！  
于是我们可以依次对[0,0],[0,1],[0,2]...[0,n]建树，如需得到[l,r]的树，只需将[0,r]和[0,l-1]两棵线段树相减即可！  
查询可以机智地使用宏定义  
```cpp
#define lv (value[ls[r]]-value[ls[l]])//相减后得到的线段树左儿子的值
#define rv (value[rs[r]]-value[rs[l]])//相减后得到的线段树右儿子的值
```
## 空间优化
然而这里有一个问题，每一个区间建立线段树，空间复杂度太大，无法接受  
怎么优化呢？  
实际上，下一棵线段树就相当于上一棵线段树进行单点更新，即[0,n]相对于[0,n-1]只是更新了[num[n],num[n]]的值而已。  
由于主席树不是完全二叉树，需要开数组保存左右儿子的编号，这里利用一下：如果更新左儿子，就把右儿子编号赋为上一棵树该节点右儿子的编号，反之也一样。这样每次建树只需新开一条链就行了 ~~有没有感觉特别机智~~   
更新
```cpp
void updata(int last/*上一棵线段树等位结点编号*/, int p, int v)//建立下一棵线段树,相当于线段树的单点更新,只需保存一条链而已
{
	ln[p] = ln[last]; rn[p] = rn[last];//这棵线段树和上一棵一样,直接赋值
	value[p] = value[last] + 1;//明显v包含在区间里,直接加一即可
	if (ln[p] == rn[p]) return;//叶节点,不用继续更新,直接返回即可
	if (v <= (ln[p] + rn[p] >> 1))//包含在左儿子的区间中
	{
		rs[p] = rs[last];//右子树(即右儿子)和上一棵线段树的一样
		ls[p] = ++cnt;//累计节点编号
		//本来更新节点的值是写在这里的,但这样根节点就更新不了了,于是写到了前面
		updata(ls[last], ls[p], v);//建立左子树
	}
	else//反之亦然同理
	{
		ls[p] = ls[last];
		rs[p] = ++cnt;
		updata(rs[last], rs[p], v);
	}
}
```
循环建树
```cpp
void build()//建立主席树
{
	root[0] = cnt;//0号根节点为空树,便于相减
	bud(0, n2 - 1, cnt);//先建一发空树
	for (int i = 0; i < n; i++)//[0,n)和(0,n]皆可,只不过是root[i-1]和root[i+1]的区别
	{
		root[i + 1] = ++cnt;//累计根节点
		updata(root[i], root[i + 1], num[i]);//更新这棵线段树
	}
}
```
## 离散化
然而还有一个问题，权值线段树的空间复杂度是与数据范围相关的，所以此处需要离散化。所谓离散化就是把一堆范围很大的数映射到一段很小的区间里  
例如对于序列：12 , 76 , 123 , 67 , 1 , 20  
排序后：1 , 12 , 20 , 67 , 76 , 123  
令：1->1 , 12->2 , 20->3 , 67->4 , 76->5 , 123->6   
原序列就变成了：2 , 5 , 6 , 4 , 1 , 3  
至于怎么搞映射？这不是map最擅长的吗（￣︶￣）↗　
```cpp
map <int, int> po/*由原值映射到离散化后的值*/, re/*由离散化后的值映射到原值*/;
sort(tmp, tmp + n);//先来一发排序
//巨坑!!tmp+n是排序区间末区间端点的下一个值的地址!!!
//我也不知道STL为什么要这样反正我就这样爆了两个点
n2 = unique(tmp, tmp + n) - tmp;//去重也一样!!!(STL的东西都是这个尿性)
for (int i = 0; i < n2; i++)//记录离散化后的数值
{
	po[tmp[i]] = i;
	re[i] = tmp[i];
}
for (int i = 0; i < n; i++)//将原值变为离散化后的值
{
	num[i] = po[num[i]];
}
```
输出答案时也别忘了搞回去
```cpp
cout << re[ans] << '\n';//输出答案,一定要离散化的数值搞回来!!!小心爆零!!!
```
# 完整代码
```cpp
/*
主席树 20191210
皮:震惊,cin和cout,竟然没有没有TLE???数据竟然没有爆int???!!!
*/
#include<iostream>
#include<map>
#include<algorithm>
#include<cstdio>
using namespace std;
int ls[20000000]/*保存节点左儿子*/, rs[20000000]/*保存节点右儿子*/,
root[200010]/*保存第一个元素到第n个数对应权值线段树的根节点*/,
value[20000000]/*保存权值线段树节点的值*/, 
ln[20000000]/*保存节点区间左端点*/, rn[20000000]/*保存节点区间右端点*/;
int cnt/*累计节点编号*/, n/*数的个数*/;
int n2/*排序去重后数的个数(离散化巨坑)*/;
int num[200010]/*保存序列*/, tmp[200010]/*便于离散化*/;
void bud(int l, int r, int p)//建立空树(便于线段树相减),同普通线段树,只是没有保存节点权值而已
{
	ln[p] = l; rn[p] = r;//显然
	if (l != r)//巨坑,否则死循环!!!
	{
		ls[p] = ++cnt;//累计子节点
		bud(l, (l + r >> 1), cnt);//递归建立左子树
		rs[p] = ++cnt;//累计子节点
		bud((l + r >> 1) + 1, r, cnt);//递归建立右子树
	}
}
void updata(int last/*上一棵线段树等位结点编号*/, int p, int v)//建立下一棵线段树,相当于线段树的单点更新,只需保存一条链而已
{
	ln[p] = ln[last]; rn[p] = rn[last];//这棵线段树和上一棵一样,直接赋值
	value[p] = value[last] + 1;//明显v包含在区间里,直接加一即可
	if (ln[p] == rn[p]) return;//叶节点,不用继续更新,直接返回即可
	if (v <= (ln[p] + rn[p] >> 1))//包含在左儿子的区间中
	{
		rs[p] = rs[last];//右子树(即右儿子)和上一棵线段树的一样
		ls[p] = ++cnt;//累计节点编号
		//本来更新节点的值是写在这里的,但这样根节点就更新不了了,于是写到了前面
		updata(ls[last], ls[p], v);//建立左子树
	}
	else//反之亦然同理
	{
		ls[p] = ls[last];
		rs[p] = ++cnt;
		updata(rs[last], rs[p], v);
	}
}
void build()//建立主席树
{
	root[0] = cnt;//0号根节点为空树,便于相减
	bud(0, n2 - 1, cnt);//先建一发空树
	for (int i = 0; i < n; i++)//[0,n)和(0,n]皆可,只不过是root[i-1]和root[i+1]的区别
	{
		root[i + 1] = ++cnt;//累计根节点
		updata(root[i], root[i + 1], num[i]);//更新这棵线段树
	}
}
//这类宏定义一定要加括号，否则死的很惨！！！！！！
//我才不会告诉你我就是因为这个第一次交爆零了...
//还有,宏定义这种东西作用范围是当前文件...写在哪里都一样...
#define lv (value[ls[r]]-value[ls[l]])//相减后得到的线段树左儿子的值
#define rv (value[rs[r]]-value[rs[l]])//相减后得到的线段树右儿子的值
int ans;//落谷猥琐巨坑,直接返回会MLE!!!被迫改void并使用全局变量保存答案
void query(int k, int l, int r)//这里的l和r指的不是数列的区间,而是l棵线段树和第r棵线段树的根节点
{
	//直接写成(其实就是)权值的查询就好
	if (ln[l] == rn[l])//叶节点,直接记录答案
	{
		ans = ln[l];
		return;
	}
	if (k <= lv)//左儿子包含的数的个数大于等于待查询的k
		query(k, ls[l], ls[r]);//向左儿子查询第k小即可
	else//左儿子包含的数的个数小于待查询的k
		query(k - lv, rs[l], rs[r]);//整段区间的第k小即为右区间的第(k-左区间包含数的个数)小
}
map <int, int> po/*由原值映射到离散化后的值*/, re/*由离散化后的值映射到原值*/;
int main()
{
	cin >> n;//输入,显然
	int m;
	cin >> m;
	for (int i = 0; i < n; i++)//输入并保存副本用于离散化
	{
		cin >> num[i];
		tmp[i] = num[i];
	}
	//---------------------------------------离散化--------------------------------------------
	sort(tmp, tmp + n);//先来一发排序
	//巨坑!!tmp+n是排序区间末区间端点的下一个值的地址!!!
	//我也不知道STL为什么要这样反正我就这样爆了两个点
	n2 = unique(tmp, tmp + n) - tmp;//去重也一样!!!(STL的东西都是这个尿性)
	for (int i = 0; i < n2; i++)//记录离散化后的数值
	{
		po[tmp[i]] = i;
		re[i] = tmp[i];
	}
	for (int i = 0; i < n; i++)//将原值变为离散化后的值
	{
		num[i] = po[num[i]];
	}
	//-----------------------------------------------------------------------------------------
	build();//建立主席树
	int l, r, k;
	while (m--)
	{
		cin >> l >> r >> k;
		l--;
		query(k, root[l], root[r]);//一定要传递根节点的编号!!!!!!
		cout << re[ans] << '\n';//输出答案,一定要离散化的数值搞回来!!!小心爆零!!!
	}
	return 0;
}
```