2020-2021:teams:legal_string:jxm2001:长链剖分
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:长链剖分 [2020/05/29 22:12] jxm2001 |
2020-2021:teams:legal_string:jxm2001:长链剖分 [2020/07/27 22:54] (当前版本) jxm2001 ↷ 页面2020-2021:teams:legal_string:长链剖分被移动至2020-2021:teams:legal_string:jxm2001:长链剖分 |
||
|---|---|---|---|
| 行 5: | 行 5: | ||
| 一种可以在线性时间复杂度维护子树中**仅限深度有关的信息**的算法，主要用于一些特殊的 $\text{dp}$ | 一种可以在线性时间复杂度维护子树中**仅限深度有关的信息**的算法，主要用于一些特殊的 $\text{dp}$ | ||
| - | ===== 算法思想 ==== | + | ===== 算法思想 ===== |
| 类似重链剖分，将儿子分为重儿子和轻儿子，重儿子组成的链构成长链 | 类似重链剖分，将儿子分为重儿子和轻儿子，重儿子组成的链构成长链 | ||
| 行 49: | 行 49: | ||
| <hidden 查看代码> | <hidden 查看代码> | ||
| <code cpp> | <code cpp> | ||
| - | #include <iostream> | ||
| - | #include <cstdio> | ||
| - | #include <algorithm> | ||
| - | #include <cstring> | ||
| - | #include <cctype> | ||
| - | #include <vector> | ||
| - | #define _for(i,a,b) for(int i=(a);i<(b);++i) | ||
| - | #define _rep(i,a,b) for(int i=(a);i<=(b);++i) | ||
| - | using namespace std; | ||
| - | typedef long long LL; | ||
| - | inline int read_int(){ | ||
| - | int t=0;bool sign=false;char c=getchar(); | ||
| - | while(!isdigit(c)){sign|=c=='-';c=getchar();} | ||
| - | while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();} | ||
| - | return sign?-t:t; | ||
| - | } | ||
| - | inline void write(LL x){ | ||
| - | register char c[21],len=0; | ||
| - | if(!x)return putchar('0'),void(); | ||
| - | if(x<0)x=-x,putchar('-'); | ||
| - | while(x)c[++len]=x%10,x/=10; | ||
| - | while(len)putchar(c[len--]+48); | ||
| - | } | ||
| - | inline void space(LL x){write(x),putchar(' ');} | ||
| - | inline void enter(LL x){write(x),putchar('\n');} | ||
| const int MAXN=5e5+5,MAXM=21; | const int MAXN=5e5+5,MAXM=21; | ||
| unsigned int s; | unsigned int s; | ||
| 行 169: | 行 144: | ||
| 给定一棵 $n$ 个结点的树，问有多少个无序点对 $(i,j,k)$ 满足 $i,j,k$ 两两间距离相等 | 给定一棵 $n$ 个结点的树，问有多少个无序点对 $(i,j,k)$ 满足 $i,j,k$ 两两间距离相等 | ||
| - | 树形$\text{dp}$，利用指针位移使得父结点以 $O(1)$ 时间继承重儿子信息，暴力继承轻儿子信息 | + | 树形$\text{dp}$，状态转移方程可以参考这份博客[[https://www.luogu.com.cn/blog/xht37/solution-p3565|详情]] |
| + | |||
| + | 利用指针位移使得父结点以 $O(1)$ 时间继承重儿子信息，暴力继承轻儿子信息 | ||
| 设当前结点为 $u$，$u$ 的儿子结点为 $x$，每次暴力继承时间复杂度为 $O\left(\text{len}\left(x\right)\right)$ | 设当前结点为 $u$，$u$ 的儿子结点为 $x$，每次暴力继承时间复杂度为 $O\left(\text{len}\left(x\right)\right)$ | ||
| 行 183: | 行 160: | ||
| <hidden 查看代码> | <hidden 查看代码> | ||
| <code cpp> | <code cpp> | ||
| - | #include <cstdio> | ||
| - | #include <algorithm> | ||
| - | #include <cstring> | ||
| - | #include <cctype> | ||
| - | #define _for(i,a,b) for(int i=(a);i<(b);++i) | ||
| - | #define _rep(i,a,b) for(int i=(a);i<=(b);++i) | ||
| - | using namespace std; | ||
| - | typedef long long LL; | ||
| - | inline int read_int(){ | ||
| - | int t=0;bool sign=false;char c=getchar(); | ||
| - | while(!isdigit(c)){sign|=c=='-';c=getchar();} | ||
| - | while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();} | ||
| - | return sign?-t:t; | ||
| - | } | ||
| - | inline void write(LL x){ | ||
| - | register char c[21],len=0; | ||
| - | if(!x)return putchar('0'),void(); | ||
| - | if(x<0)x=-x,putchar('-'); | ||
| - | while(x)c[++len]=x%10,x/=10; | ||
| - | while(len)putchar(c[len--]+48); | ||
| - | } | ||
| - | inline void space(LL x){write(x),putchar(' ');} | ||
| - | inline void enter(LL x){write(x),putchar('\n');} | ||
| const int MAXN=5e5+5; | const int MAXN=5e5+5; | ||
| struct Edge{ | struct Edge{ | ||
2020-2021/teams/legal_string/jxm2001/长链剖分.1590761571.txt.gz · 最后更改: 2020/05/29 22:12 由 jxm2001
