【学习笔记】(19) 启发式合并
启发式合并
启发式合并核心思想就一句话：把小集合的合并到大的里。
启发式合并思想可以放到很多数据结构里，链表、线段树、甚至平衡树都可以。
考虑时间复杂度，设总共有 \(n\) 个元素，由于每次集合的大小至少翻倍，所以至多会合并 \(logn\) 次，总的复杂度就是 \(O(nlogn)\) 的（结合线段树合并就是 \(O(nlog^2n)\) 的）
dsu on tree 就是树上启发式合并。
dsu on tree 优雅的思想
对于以 u 为根的子树
①. 先统计它轻子树(轻儿子为根的子树)的答案，统计完后删除信息
②. 再统计它重子树(重儿子为根的子树)的答案 ，统计完后保留信息
③. 然后再将重子树的信息合并到 u上
④. 再去遍历 u 的轻子树，然后把轻子树的信息合并到 u 上
⑤. 判断 u 的信息是否需要传递给它的父节点（u 是否是它父节点的重儿子）
dsu on tree 暴力的操作体现于统计答案上（不同的题目统计方式不一样）
例题
Ⅰ.CF570D Tree Requests
重排之后能否构成回文串，即判断出现次数为奇数的字符个数是否小于等于1
因为要多次询问以某个点为根深度为 \(b\) 的节点上的字母
所以可以对每个节点开个 vector，再把和它有关的询问保存在vector
然后在 dsu on tree 的过程进行到该节点时遍历这个节点的 vector (相关询问)
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
using namespace std;
const int N = 1e6 + 67;
int read(){
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
return x * f;
}
int n, m, tot;
int Head[N], to[N], Next[N];
int a[N], son[N], sz[N], d[N];
vector<pair<int, int> > Q[N];
bool vis[N];
int b[N][26], ct[N], ans[N];
void add(int u, int v){
to[++tot] = v, Next[tot] = Head[u], Head[u] = tot;
}
void dfs1(int x, int fa){
d[x] = d[fa] + 1, sz[x] = 1;
for(int i = Head[x]; i; i = Next[i]){
int y = to[i]; if(y == fa) continue;
dfs1(y, x), sz[x] += sz[y];
if(sz[y] > sz[son[x]]) son[x] = y;
}
}
void calc(int x, int fa){
if(b[d[x]][a[x]]) ct[d[x]]--;
else ct[d[x]]++;
b[d[x]][a[x]] ^= 1;
for(int i = Head[x]; i; i = Next[i]){
int y = to[i]; if(y == fa || vis[y]) continue;
calc(y, x);
}
}
void dfs2(int x, int fa, int opt){
for(int i = Head[x]; i; i = Next[i]){
int y = to[i]; if(y == fa || y == son[x]) continue;
dfs2(y, x, 0);
}
if(son[x]) dfs2(son[x], x, 1), vis[son[x]] = 1;
calc(x, fa), vis[son[x]] = 0;
for(auto it : Q[x])
ans[it.second] = (ct[it.first] <= 1);
if(!opt) calc(x, fa);
}
int main(){
n = read(), m = read();
for(int i = 2; i <= n; ++i){
int u = read();
add(u, i), add(i, u);
}
for(int i = 1; i <= n; ++i) {
char ch; cin >> ch;
a[i] = ch - 'a';
}
for(int i = 1; i <= m; ++i){
int u = read(), k = read();
Q[u].pb(mp(k, i));
}
dfs1(1, 0), dfs2(1, 0, 0);
for(int i = 1; i <= m; ++i)
printf("%s\n", ans[i] ? "Yes" : "No");
return 0;
}
Ⅱ.CF375D Tree and Queries
开个数组 \(cnt_i\) 表示 \(i\) 种颜色有多少个，\(f_i\) 表示数量大于 \(i\) 的有多少种。
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
using namespace std;
const int N = 2e5 + 67;
int read(){
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
return x * f;
}
int n, m, tot;
int fa[N], sz[N], son[N];
int c[N], cnt[N], ans[N], f[N];
int Head[N], to[N], Next[N];
vector<pii> Q[N];
bool vis[N];
void add(int u, int v){
to[++tot] = v, Next[tot] = Head[u], Head[u] = tot;
}
void dfs1(int x, int f){
fa[x] = f, sz[x] = 1;
for(int i = Head[x]; i; i = Next[i]){
int y = to[i]; if(y == fa[x]) continue;
dfs1(y, x); sz[x] += sz[y];
if(sz[y] > sz[son[x]]) son[x] = y;
}
}
void calc(int x, int val){
if(val == 1) f[cnt[c[x]] += val]++;
else --f[cnt[c[x]]], cnt[c[x]] += val;
for(int i = Head[x]; i; i = Next[i]){
int y = to[i]; if(y == fa[x] || vis[y]) continue;
calc(y, val);
}
}
void dfs2(int x, int opt){
for(int i = Head[x]; i; i = Next[i]){
int y = to[i]; if(y == fa[x] || y == son[x]) continue;
dfs2(y, 0);
}
if(son[x]) dfs2(son[x], 1), vis[son[x]] = 1;
calc(x, 1), vis[son[x]] = 0;
for(auto it : Q[x])
ans[it.second] = f[it.first];
if(!opt) calc(x, -1);
}
int main(){
n = read(), m = read();
for(int i = 1; i <= n; ++i) c[i] = read();
for(int i = 1; i < n; ++i){
int u = read(), v = read();
add(u, v), add(v, u);
}
for(int i = 1; i <= m; ++i){
int u = read(), k = read();
Q[u].pb(mp(k, i));
}
dfs1(1, 0), dfs2(1, 0);
for(int i = 1; i <= m; ++i) printf("%d\n", ans[i]);
return 0;
}
Ⅲ. P4149 [IOI2011] Race
树上两点 \(u,v\) 的距离为 \(dis_u + dis_v - 2 \times dis_{lca(u,v)}\)，边的数量为 \(d_u + d_v - 2 \times d_{lca(u,v}\) 。
那么问题就转换成在树上找到两点 \(u,v\) 使得 \(dis_u+dis_v−2×dis_{lca(u,v)}=k\) 且 \(d_u+d_v−2×d_{lca(u,v)}\) 尽可能小。
于是我们可以定义 \(minn_d\) 表示当前距离 \(1\) 号点距离为 \(d\) 的节点的最小深度。
因为我们计算两点的简单路径权值和、两点简单路径的边的个数是根据它们的lca ，所以一个分支内的节点不能相互影响
所以需要先对一个分支统计完贡献后，再添加它的信息
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define int long long
using namespace std;
const int N = 5e5 + 67;
int read(){
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
return x * f;
}
int n, m, k, tot, ans = 0x3f3f3f3f3f3f3f3f;
int fa[N], sz[N], son[N], d[N], dis[N];
int Head[N], to[N], Next[N], edge[N];
map<int, int> minn;
void add(int u, int v, int w){
to[++tot] = v, Next[tot] = Head[u], Head[u] = tot, edge[tot] = w;
}
void dfs1(int x, int f){
fa[x] = f, sz[x] = 1, d[x] = d[f] + 1;
for(int i = Head[x]; i; i = Next[i]){
int y = to[i]; if(y == fa[x]) continue;
dis[y] = dis[x] + edge[i], dfs1(y, x), sz[x] += sz[y];
if(sz[y] > sz[son[x]]) son[x] = y;
}
}
void calc(int x, int rt){
int s = k + 2 * dis[rt] - dis[x];
if(minn.count(s)) ans = min(ans, minn[s] + d[x] - d[rt] * 2);
for(int i = Head[x]; i; i = Next[i]){
int y = to[i]; if(y == fa[x]) continue;
calc(y, rt);
}
}
void change(int x){
if(minn.count(dis[x])) minn[dis[x]] = min(minn[dis[x]], d[x]);
else minn[dis[x]] = d[x];
for(int i = Head[x]; i; i = Next[i]){
int y = to[i]; if(y == fa[x]) continue;
change(y);
}
}
void dfs2(int x, int opt){
for(int i = Head[x]; i; i = Next[i]){
int y = to[i]; if(y == fa[x] || y == son[x]) continue;
dfs2(y, 0);
}
if(son[x]) dfs2(son[x], 1);
int s = k + dis[x];
if(minn.count(s)) ans = min(ans, minn[s] - d[x]);minn[dis[x]] = d[x];
for(int i = Head[x]; i; i = Next[i]){
int y = to[i]; if(y == fa[x] || y == son[x]) continue;
calc(y, x), change(y);
}
if(!opt) minn.clear();
}
signed main(){
n = read(), k = read();
for(int i = 1; i < n; ++ i){
int u = read() + 1, v = read() + 1, w = read();
add(u, v, w), add(v, u, w);
}
dfs1(1, 0), dfs2(1, 0);
printf("%lld\n", ans == 0x3f3f3f3f3f3f3f3f ? -1 : ans);
return 0;
}