menu zcmimi's blog

arrow_back 静态链分治

先离散化权值为排名,从大到小排序

遍历所有点,用权值树状数组统计,结果是 遍历完该子树后答案 - 遍历该子树前答案

(为什么一开始会去想什么dsu on tree和线段树合并 ```cpp

in

zc
2020-03-01 19:36

题意

一棵以1为根的树,每个节点上都有1个字母,有m个询问。每次询问v对应的子树中,深度为h的这层节点的字母,能否打乱重排组成回文串。根的深度为1,每个点的深度为到根的距离。

zc
2019-12-21 19:47

好题!

重新排序后能变成回文串,出现次数为奇数的字母最多只能有一种

因为只有22种字符所以我们可以用状态压缩来记录每种字母出现的次数是奇数或者偶数

设路径端点的两端为x,y,d_x

zc
2019-12-21 19:47

倍增找k级祖先+dsu on tree静态链分治

设当前节点为x

如果d_x < k,那么答案当然为0 可以找到第k级祖先,然后在k级祖先上添加一组询问(求它子树中

zc
2019-12-21 19:47

静态链分治 参见模板

```cpp

include<bits/stdc++.h>

namespace ZDY{

#pragma GCC optimize(3)
#define il
zc
2019-12-21 19:47

静态链分治

记得开long\ long ```cpp

include<bits/stdc++.h>

namespace ZDY{

#pragma GCC optimize(3)
zc
2019-12-21 19:47
1 / 1
Search
search