2020-2021:teams:legal_string:lgwza:虚树
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:lgwza:虚树 [2020/09/10 22:08] lgwza [推荐习题] |
2020-2021:teams:legal_string:lgwza:虚树 [2021/03/06 19:03] (当前版本) lgwza |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| ====== 虚树 ====== | ====== 虚树 ====== | ||
| - | ===== 印子 ===== | + | ===== 引子 ===== |
| 行 150: | 行 150: | ||
| 我们用黄色的点代表在栈内的点，绿色的点代表从栈中弹出的点。 | 我们用黄色的点代表在栈内的点，绿色的点代表从栈中弹出的点。 | ||
| - | * 取序列中第一个作为当前节点，也就是 $4$。再取栈顶元素，为 $1$。求 $1$ 和 $4$ 的 $LCA$：$LCA(1,4)=1$ 。 | + | * 取序列中第一个作为当前节点，也就是 $4$。再取栈顶元素，为 $1$。求 $1$ 和 $4$ 的 $LCA$：$LCA(1,4)=1$ 。 |
| * 发现 $LCA(1,4)=$ 栈顶元素，说明它们在虚树的一条链上，所以直接把当前节点 $4$ 入栈，当前栈为 $4,1$。 | * 发现 $LCA(1,4)=$ 栈顶元素，说明它们在虚树的一条链上，所以直接把当前节点 $4$ 入栈，当前栈为 $4,1$。 | ||
| 行 235: | 行 235: | ||
| * [[https://darkbzoj.tk/problem/2286|「SDOI2011」消耗战]] | * [[https://darkbzoj.tk/problem/2286|「SDOI2011」消耗战]] | ||
| * [[https://darkbzoj.tk/problem/3611|「HEOI2014」大工程]] | * [[https://darkbzoj.tk/problem/3611|「HEOI2014」大工程]] | ||
| - | * [[http://codeforces.com/contest/613/problem/D/| CF613D Kingdom and its Cities]] | + | * [[http://codeforces.com/contest/613/problem/D/| CF613D Kingdom and its Cities]] |
| * [[https://darkbzoj.tk/problem/3572|「HNOI2014」世界树]] | * [[https://darkbzoj.tk/problem/3572|「HNOI2014」世界树]] | ||
2020-2021/teams/legal_string/lgwza/虚树.1599746895.txt.gz · 最后更改: 2020/09/10 22:08 由 lgwza
