2020-2021:teams:legal_string:jxm2001:lct
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:lct [2021/07/08 20:00] jxm2001 |
2020-2021:teams:legal_string:jxm2001:lct [2021/07/11 16:30] (当前版本) jxm2001 [子树信息维护] |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | ====== 动态树 ====== | + | ====== LCT ====== |
| ===== 算法简介 ===== | ===== 算法简介 ===== | ||
| - | 动态树简称 LCT ，是一种动态维护森林连通性、路径信息的数据结构，时间复杂度为 $O\left(n\log n\right)$ | + | LCT 是一种动态维护森林连通性、路径信息的数据结构，时间复杂度为 $O\left(n\log n\right)$。 |
| ===== 算法思想 ===== | ===== 算法思想 ===== | ||
| 行 993: | 行 993: | ||
| [[https://www.luogu.com.cn/problem/P3379|洛谷p3379]] | [[https://www.luogu.com.cn/problem/P3379|洛谷p3379]] | ||
| - | $\text{LCT}$ 本身支持换根，所以只需要怎么考虑求 $\text{LCA}$(u,v)。 | + | $\text{LCT}$ 本身支持换根，所以只需要怎么考虑求 $\text{LCA}(u,v)$。 |
| 考虑先 $\text{access}(u)$ 这样根节点到 $u$ 的路径变实边，于是根节点到 $v$ 的路径的第一条虚边一定从 $\text{LCA}(u,v)$ 出发。 | 考虑先 $\text{access}(u)$ 这样根节点到 $u$ 的路径变实边，于是根节点到 $v$ 的路径的第一条虚边一定从 $\text{LCA}(u,v)$ 出发。 | ||
| 行 1267: | 行 1267: | ||
| ==== 子树信息维护 ==== | ==== 子树信息维护 ==== | ||
| + | |||
| + | [[https://www.luogu.com.cn/problem/P4219|洛谷p4219]] | ||
| + | |||
| + | **题意** | ||
| + | |||
| + | 给定 $n$ 个点，给定两种操作： | ||
| + | |||
| + | - 加边操作，保证加边后不会出现环 | ||
| + | - 询问经过 $(u,v)$ 边的路径数 | ||
| + | |||
| + | **题解** | ||
| 子树信息需要维护虚儿子和实儿子信息和，实儿子利用 $\text{ch}(k,0/1)$ 维护，虚儿子只需要额外记录即可。 | 子树信息需要维护虚儿子和实儿子信息和，实儿子利用 $\text{ch}(k,0/1)$ 维护，虚儿子只需要额外记录即可。 | ||
| 行 1302: | 行 1313: | ||
| 注意，如果需要维护点权极值等信息时，可以用 $\text{set}$ 维护 $si[k]$。 | 注意，如果需要维护点权极值等信息时，可以用 $\text{set}$ 维护 $si[k]$。 | ||
| - | |||
| - | [[https://www.luogu.com.cn/problem/P4219|洛谷p4219]] | ||
| - | |||
| - | **题意** | ||
| - | |||
| - | 给定 $n$ 个点，给定两种操作： | ||
| - | |||
| - | - 加边操作，保证加边后不会出现环 | ||
| - | - 询问经过 $u\to v$ 边的路径数 | ||
| - | |||
| - | **题解** | ||
| 不难发现，对询问操作，可以先断开 $u,v$，则答案为 $\text{sz}(u)\times \text{sz}(v)$。 | 不难发现，对询问操作，可以先断开 $u,v$，则答案为 $\text{sz}(u)\times \text{sz}(v)$。 | ||
2020-2021/teams/legal_string/jxm2001/lct.1625745651.txt.gz · 最后更改: 2021/07/08 20:00 由 jxm2001
