menu zcmimi's blog

arrow_back dfs序

1 x表示把点x到根节点的路径上所有的点染上一种没有用过的新颜色

从这里可以看出每种颜色在树上都是一条链的形式存在

可以发现这和LCT很像

那么1操作可以看成access操作

zc
2020-04-12 15:41

dfs序作为下标,深度作为时间轴

```cpp

include<bits/stdc++.h>

namespace ZDY{

#pragma GCC optimize(3)
#de
zc
2020-01-18 22:40

a是确定的,考虑b的情况:

  1. a的祖先

    可以作为b的点的数量是\min(d_x,k)(d_xx的深度),

    a的子树中除a外其他点都可

zc
2020-01-18 22:40

解法1

主席树+离散化(深度太大需要离散化)

```cpp

include<bits/stdc++.h>

namespace ZDY{

#pragma GCC optimize(3
zc
2019-12-31 11:31

线段树解法:

我们记录d_x表示x的深度还有dfs

每个点修改的时候把它的子树都加上val

因为记录了深度,所以d_{x'}如果和d_x同奇偶则加上val,

zc
2019-12-21 19:47
1 / 1
Search
search