New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

2022-9-13总结 | Ptilopsis_w's little blog #26

Open

Ptilopsisw opened this issue Sep 15, 2022 · 0 comments

Labels

4d227ba15691ae8d2e802a3a907ba39a Gitalk

Owner

Ptilopsisw commented Sep 15, 2022

https://ptilopsisw.github.io/2022/09/14/2022-9-13%E6%80%BB%E7%BB%93/

tree 考虑怎么询问一个点 xxx 的编号最大的祖先，可以先把树拍到 dfs 序上，用每个节点的编号在它的子树里取 max⁡\maxmax，然后查询 dfn[x]dfn[x]dfn[x] 处的 max⁡\maxmax 值即为 xxx 的编号最大的祖先。而这时我们还需要保证取到的 max⁡\maxmax 值在另一棵树上是 yyy 的祖先，我们可以只把 yyy 的祖先插入到线段树中，这样询问出来的

Ptilopsisw added Gitalk 4d227ba15691ae8d2e802a3a907ba39a labels

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment