2020-2021:teams:legal_string:lgwza:虚树
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:lgwza:虚树 [2020/09/10 22:00] lgwza 创建 |
2020-2021:teams:legal_string:lgwza:虚树 [2021/03/06 19:03] (当前版本) lgwza |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| ====== 虚树 ====== | ====== 虚树 ====== | ||
| - | ===== 印子 ===== | + | ===== 引子 ===== |
| - | <HTML><blockquote> | ||
| [[https://www.luogu.com.cn/problem/P2495|「SDOI2011」消耗战]] | [[https://www.luogu.com.cn/problem/P2495|「SDOI2011」消耗战]] | ||
| 行 29: | 行 29: | ||
| 对于 $100\%$ 的数据，$2\le n\le 2.5\times10^5,\sum k_i\le 5\times10^5,1\le k_i\le n-1$ 。 | 对于 $100\%$ 的数据，$2\le n\le 2.5\times10^5,\sum k_i\le 5\times10^5,1\le k_i\le n-1$ 。 | ||
| - | </blockquote></HTML> | + | |
| ===== 虚树 Virtual Tree ===== | ===== 虚树 Virtual Tree ===== | ||
| 行 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/虚树.1599746403.txt.gz · 最后更改: 2020/09/10 22:00 由 lgwza
