menu zcmimi's blog

arrow_back

交互题

我们从叶子节点开始搜索,把所有叶子节点添加到队列中

每次从队列中弹出两个叶子节点,

如果lca为其中一个,那么这个lca就是树根

否则删除这两个节点,可能会形成新的叶子节点,加

zc
2020-05-03 11:51

可以发现有三种路径:

  1. a \leftrightarrow b

  2. $a \leftrightarrow x \leftrightarrow y \leftrightarrow b

zc
2020-05-03 11:09

可以发现,这条链必然经过每个给定点的父亲

把每个给定点都变成它的父亲

按深度排序

依次判断接下来的节点是否在上一个的子树中即可 ```cpp

include<bits/stdc++.h>

d

zc
2020-04-27 17:49

Dynamic Rankings为例:

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

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

zcmimi
2020-02-01

换根树链剖分

loj #139.树链剖分

前置知识:树链剖分

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

树链加、查询树

zcmimi
2020-01-30

形态: 在一棵树上加多一条边

实现:

找出环后一次处理环上每个点的子树,然后再处理环

[IOI 2008]Island(求基环树直径)

[IOI 2008 Island](https:/

zcmimi
2020-01-02

kruskal重构树

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

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

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

否则连接x,y

$krus

zcmimi
2019-12-25

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

静态链分治是离线算法,有点像莫队,复杂度

zcmimi
2019-11-11

点分治

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

树的重心

树的最大子树最小的点

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

```cpp int rt,mxs=inf,siz[N];

zcmimi
2019-11-01

建树

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

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

![](https://images.cnblogs.com/cnblogs_com/sdzwyq/

zcmimi
2019-01-30
1 / 2
Search
search