zcmimi's blog

arrow_back共16篇文章

avatar
zcmimi
2020-09-28 14:07:23

prufer序列

这是一种将带标号的树用一个唯一的整数序列表示的方法.

很多与度数有关的树上计数问题,都可以用它以及它的性质来解决

avatar
zcmimi
2020-09-25 14:51:21

虚树是一种统计树上信息的技术

例题: LG 2495 [SDOI2011]消耗战

如果树的点数很少,可以直接树上dp

可以发现\sum k_i \le 5 \times 10^5

我们可以每次都把提供

avatar
zcmimi
2020-02-01

Dynamic Rankings为例:

如果不带修改,那就是普通的主席树

待修改: 树状数组套动态开点权值线段树

对于修改a_p,

受影响的有[p,n]

但是我们不需要从p修改到n

可以

avatar
zcmimi
2020-01-30

换根树链剖分

loj #139.树链剖分

前置知识:树链剖分

题意:树链加,子树加,需要支持换根,查询树链和,子树和

树链加、查询树链和 与普通的树链剖分一样

主要讲:

需要支持换根,子树加,查询子树和

设当前查询的点为x

kruskal重构树

我们回想一下kruskal生成最小生成树的过程:

先将边按边权从小到大排序,然后依次加入

如果x,y已经联通,则跳过这条边

否则连接x,y

kruskal重构树是在kruskal生成最小生成树的,

连接x,y时,将边权变成一个新的节点$

avatar
zcmimi
2019-11-11

静态链分治用于解决静态树上众数问题,比如Codeforces\ 600E

静态链分治是离线算法,有点像莫队,复杂度\Theta (n \log n \log n)

比如说遍历一遍子树可以得出答案,但是每棵子树

avatar
zcmimi
2019-11-01

点分治

点分治用于大规模处理树上路径

树的重心

树的最大子树最小的点

性质:每一个子树的大小都不超过\frac n2

```cpp int rt,mxs=inf,siz[N];// 当前 根,最大子树大小 void frt(int x,int f){ siz[x]=1

avatar
zcmimi
2019-01-30

建树

tarjan求出双连通分量后把其中的点连向新建的节点

建成的新图(树)即为圆方树

**性质:可

avatar
zcmimi
2019-01-20 00:23:01

二维线段树一般用线段树套线段树写,当然也可以用四叉树

树套树,顾名思义,外层树的每个节点都是一棵树。

[题目地址:https://www.luogu.org/problemnew/

avatar
zcmimi
2019-01-20 00:22:39
1/2
Search
search