【学习笔记】树上启发式合并(dsu on tree) · 2

主要就是整理一下dsu on tree的进阶版习题。

$0x01$ $\rm Cf375D$ Tree and Queries

给出一棵$n$个结点的树,每个结点有一个颜色$c_i$ 。 询问$q$次,每次询问以$v$结点为根的子树中,出现次数 $≥k$的颜色有多少种。树的根节点是$1$。

考虑维护子树里面每种颜色出现的次数,但是显然询问的是一个$buc[c_i]$的后缀和,于是考虑上线段树来维护这个东西,calc到每个点的时候先del掉原来的再upd新的信息……然后就做完了233

然而一开始的时候我调了好久,因为我是这么写的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void do_do(int u, int fa){
ts[base[u]] ++ ;
for (int k = head[u] ; k ; k = E[k].next)
if (to(k) != fa && !vis[to(k)]) do_do(to(k), u) ;
}
void do_del(int u, int fa){
ts[base[u]] -- ;
for (int k = head[u] ; k ; k = E[k].next)
if (to(k) != fa && !vis[to(k)]) do_del(to(k), u) ;
}
void _count(int u, int fa, int val){
bool fg = 1 ;
if (!chk[base[u]])
chk[base[u]] = 1,
update(1, 1, N, ts[base[u]] + 1, val), fg = 0 ;
for (int k = head[u] ; k ; k = E[k].next)
if (to(k) != fa && !vis[to(k)]) _count(to(k), u, val) ;
if (!fg) chk[base[u]] = 0 ;
}
void calc(int u, int fa){
_count(u, fa, -1) ; do_do(u, fa) ; _count(u, fa, 1) ;
}
void del(int u, int fa){
_count(u, fa, -1) ; do_del(u, fa) ; _count(u, fa, 1) ;
}

看上去很对的亚子,但是错就错在必须每个点独立计算完贡献才能考虑下一个点,否则下一个点的信息就是错误的——也就是说不能整体del再整体upd,必须逐个逐个的delupd。。然而事实上关键问题还是在$buc$的统计上出了问题233

于是最后的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void calc(int u, int fa){
update(1, 1, N, ts[base[u]] + 1, -1) ;
ts[base[u]] ++ ;
update(1, 1, N, ts[base[u]] + 1, 1) ;
for (int k = head[u] ; k ; k = E[k].next)
if (to(k) != fa && !vis[to(k)]) calc(to(k), u) ;
}
void del(int u, int fa){
update(1, 1, N, ts[base[u]] + 1, -1) ;
ts[base[u]] -- ;
update(1, 1, N, ts[base[u]] + 1, 1) ;
for (int k = head[u] ; k ; k = E[k].next)
if (to(k) != fa && !vis[to(k)]) del(to(k), u) ;
}
void dfs(int u, int fa, int mk){
for (int k = head[u] ; k ; k = E[k].next)
if (to(k) != fa && to(k) != son[u]) dfs(to(k), u, 0) ;
if (son[u])
dfs(son[u], u, 1), vis[son[u]] = 1 ;
calc(u, fa) ;
for (int k = 0 ; k < qs[u].size() ; ++ k)
ans[u].pb(query(1, 1, N, qs[u][k] + 1, N)) ;
vis[son[u]] = 0 ; if (!mk) del(u, fa) ;
}

$0x02$ $\rm Cf741D$ Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths

一棵根为$1$的树,每条边上有一个字符($a-v$共$22$种)。 一条简单路径被称为$\rm Dokhtar-kosh$当且仅当路径上的字符经过重新排序后可以变成一个回文串。 求每个子树中最长的$\rm Dokhtar-kosh$路径的长度。

似乎是Cf570D的升级版,因为路径可以跨过根所以会显得比较复杂,不过结论还是可以用的:

我们令一个字符的权值$val(x)=\text{1<<(x-‘a’)}$,那么对与一个串$\rm S$,我们令$k=\rm{Xor}_{i=1}^n\it val\rm( S[i])$,那么重排之后可以构成回文串$\Longleftrightarrow$ $size(k)\leq 1$,其中$size(\rm S)$指集合$\rm S$内的元素个数,也就是二进制表示中$1$的个数

然后就是考虑怎么维护这个东西。

  • 不经过根的路径,分治做下去就好,每一层$u$对所有的$son[u]$的$ans$取$\max$.

  • 经过根的路径,发现对于一个$u$,和$v$组合后可以产生贡献,我们只需要关心深度最大的$v$.所以自然想到用一个桶来维护二进制数值的最大深度。但是这个地方还有个问题,就是统计路径的话,$u$和$v$不能在同一棵子树中,容易发现只要满足不在同一棵子树中,那就一定满足$(u,v)$这条路径经过$root$。所以这个地方,对于一个点$u$,考虑一棵子树一棵子树地计算答案,深度做差求;而“经过根节点的路径”包括起点和终点在根节点上的路径,所以需要对$root$单独计算一次。

看上去应该这么实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
void _delete(int u, int fa){
f[dis[u]] = 0 ;
for (int k = head[u] ; k ; k = E[k].next)
if (to(k) != fa && !vis[to(k)]) _delete(to(k), u) ;
}
void calc(int u, int fa, int & ans, int d){
if (f[dis[u]])
ans = max(ans, f[dis[u]] + dep[u] - 2 * d) ;
for (int i = 0 ; i <= 21 ; ++ i)
if (f[dis[u] ^ (1 << i)])
ans = max(ans, f[dis[u] ^ (1 << i)] + dep[u] - 2 * d) ;
for (int k = head[u] ; k ; k = E[k].next)
if (to(k) != fa && !vis[to(k)]) calc(to(k), u, ans, d) ;
}
void update(int u, int fa){
f[dis[u]] = max(f[dis[u]], dep[u]) ;
for (int k = head[u] ; k ; k = E[k].next)
if (to(k) != fa && !vis[to(k)]) update(to(k), u) ;
}
void dfs(int u, int fa, int mk){
for (int k = head[u] ; k ; k = E[k].next){
if (to(k) == fa || to(k) == son[u]) continue ;
dfs(to(k), u, 0), ans[u] = max(ans[u], ans[to(k)]) ;
}
if (son[u])
dfs(son[u], u, 1), vis[son[u]] = 1,
ans[u] = max(ans[u], ans[son[u]]) ;
for (int k = head[u] ; k ; k = E[k].next)
if (to(k) != son[u] && to(k) != fa)
calc(to(k), u, ans[u], dep[u]), update(to(k), u) ;
if (f[dis[u]])
ans[u] = max(ans[u], f[dis[u]] - dep[u]) ;
for (int i = 0 ; i <= 21 ; ++ i)
if (f[dis[u] ^ (1 << i)])
ans[u] = max(ans[u], f[dis[u] ^ (1 << i)] - dep[u]) ;
f[dis[u]] = max(f[dis[u]], dep[u]) ; vis[son[u]] = 0 ; if (!mk) _delete(u, fa) ;
}

总感觉……复杂度不是很对?感觉单次运行dfs复杂度很高的亚子……然而还是套用“一个点到根节点最多有$\log n $个轻祖先”这个理论,每个点被访问的次数还是不变的——毕竟子树之间访问不会重复。于是时间复杂度$n\log n$。

唔,感觉这个题还是比较有技巧性的233

$0x03$ $\rm NOIP2018$模拟 · 树

这道题是从一个神仙的blog里嫖来的,提交的话可以到Luogu上提交:$\rm Link$

题面:

给定一棵树。

令$[L,R]$描述的是序号在$[L,R]$内的点的集合。

同时,令函数$\boldsymbol F(\{ \rm S\})$表示令集合$\rm S$内的点联通的需要的最小边数。

问题则是求:

$n\leq 100,000$


一步转化成求每条边的贡献。结合正难则反可知,一条边的总贡献至多是$\binom{n}{2}$,算多了的集合是那些位于这条边两侧中的其中一侧,不经过这条边的集合。所以考虑分别维护子树内和子树外的两个答案。

子树内的比较容易维护,考虑假设现在有了$\{1,2,3\},\{5,6\}$两个集合,将其视作两个连通块,当加进来$\{4\}$时,会和左右都相连接,不妨假设先与$\{1,2,3\}$合并,那么最后会产生$(1,4),(2,4),(3,4)$三个新的连通块,原来的依旧要加入。所以考虑用并查集+并查集的$size$来维护。由于子树内的点在暴力时只会插入不会删除,所以并查集是$\rm van$全没问题的。

之后是子树外的。子树外的和子树内的情况差不多,但是由插入变成了删除。然后就可以考虑用set维护,因为这东西自带的单调性比较nice,并且支持删除操作。所以流程大概就是考虑把删除的点丢到set里面,最初的ans_out显然是$\binom{n}{2}$,每删除一个新的点,设其编号为$x$,set里面第一个比$x$小的元素设为$x_p$第一个比$x$大的元素设为$x_s$,那么$[x_{p}+1,x-1]$还是连续的,$[x+1,x_s-1]$还是连续的,所以新的贡献变成了

原来的旧贡献$calc(x_s-1-(x_p+1)+1)$理应减去。

所以就做完了,感觉神清气爽,总体来说算是一道很好的题吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
set <int> s ;
int vis[MAXN], op[MAXN] ;
LL calc(LL x){ return x * (x - 1) / 2 ; }
void _clear(){
s.clear() ;
ansout = calc(N), ansin = 0,
s.insert(0), s.insert(N + 1) ;
}
int _find(int x){
return x == fr[x] ? x : fr[x] = _find(fr[x]) ;
}
void fuck(int u){
s.insert(u) ; op[u] = 1 ;
set <int> :: iterator l, r, mid ;
l = r = mid = s.find(u), l --, r ++ ;
ansout += calc(*r - *mid - 1) + calc(*mid - *l - 1) - calc(*r - *l - 1) ;
if (op[u - 1]){
int f1 = _find(u - 1), f2 = _find(u) ;
ansin += bg[f1] * bg[f2], fr[f1] = f2, bg[f2] += bg[f1] ;
}
if (op[u + 1]){
int f1 = _find(u + 1), f2 = _find(u) ;
ansin += bg[f1] * bg[f2], fr[f1] = f2, bg[f2] += bg[f1] ;
}
}
void _update(int u, int fa){
fuck(u) ; //cout << u << endl ;
for (int k = head[u] ; k ; k = E[k].next)
if (to(k) == fa || vis[to(k)]) continue ; else _update(to(k), u) ;
}
void _delete(int u, int fa){
op[u] = 0, fr[u] = u, bg[u] = 1 ;
for (int k = head[u] ; k ; k = E[k].next)
if (to(k) == fa) continue ; else _delete(to(k), u) ; // 1
}
void dfs(int u, int fa, int mk){
for (int k = head[u] ; k ; k = E[k].next){
if (to(k) == fa || to(k) == son[u]) continue ;
dfs(to(k), u, 0) ;
}
if (son[u]) dfs(son[u], u, 1), vis[son[u]] = 1 ;
_update(u, fa), ans += calc(N) - ansout - ansin ;
if (!mk) _delete(u, fa), _clear() ; vis[son[u]] = 0 ;
}

$\rm Warning$

  • 注意一个地方:

    1
    vis[son[u]] = 0 ; if (!mk) _delete(u, fa) ;

    把这两句写反了会调一下午,欢迎尝试quq