@[TheOrnateJade_ofSun](/space/show?uid=134876) 注释里面写了。。是求$\log_2$的
另外题解写复杂了,可以直接写为:
```cpp
for(int i=2;i<=n;++i)
lg[i] = lg[i>>1]+1;
```
by NaCly_Fish @ 2019-05-09 20:05:48
@[TheOrnateJade_ofSun](/space/show?uid=134876)
```lg[x]``` 数组表示 $\log_2 x$ 向下取整的值
$lg[depth[x]]$ 表示从结点 $x$ 暴力条 $2^j$ 次父亲的最大 $j$
公式为 $lg[x]=lg[\frac x 2]+1$ ,显然
by hsfzLZH1 @ 2019-05-09 20:08:16
@[hsfzLZH1](/space/show?uid=43486) 就是表示x跳最多跳2的j次方嘛?
by Grussg @ 2019-05-09 20:15:31
那lg[depsth[x]-depth[y]]是什么意思呢
by Grussg @ 2019-05-09 20:16:44
深度差的lg
即向上跳一次合法的最大深度对应的fa下标
by h2o2_ioi @ 2019-05-09 20:18:34
@[TheOrnateJade_ofSun](/space/show?uid=134876)
那一部分代码的意思是要先把 $x$ 的深度上跳到和 $y$ 一样深
$qwq=lg[dep[x]-dep[y]]$ 的意义是暴力跳 $2^{qwq}$ 次父亲不会超过 $y$ 的深度, $qwq$ 又最大
by hsfzLZH1 @ 2019-05-09 20:26:31
@[hsfzLZH1](/space/show?uid=43486) 谢谢,弄懂了
by Grussg @ 2019-05-09 20:33:35
@[卡常出奇迹](/space/show?uid=194627) 谢谢,弄懂了
by Grussg @ 2019-05-09 20:33:44
@[NaCly_Fish](/space/show?uid=115864) 谢谢,弄懂了
by Grussg @ 2019-05-09 20:33:52