首页 > 其他分享 >「笔记」dsu on tree

「笔记」dsu on tree

时间：2024-01-24 11:46:04浏览次数：20  
标签：int dsu tree 笔记 son operatorname 节点

目录

写在前面

高产似那啥。

还以为这东西是啥科技呃呃，原来是能证明复杂度的乱搞。

所以重链剖分就是动态 dsu（精神错乱

引入

dsu on tree，即树上启发式合并。

启发式算法是基于人类的经验和直观感觉，对一些算法的优化。

众所周知有启发式搜索，在搜索时增加估价函数来判断应当向哪个方向深入以优化搜索树的深度；非路径压缩的并查集的按秩合并可以尽可能地减少树高以方便查询祖先。

也就是乱搞（确信

树上启发式合并

树上启发式合并（dsu on tree）对于某些树上离线问题，可以速度大于等于大部分算法且更易于理解和实现的算法。

一道典中典题：

给定一棵 \(n\) 个节点的以 1 为根的树，节点 \(i\) 有颜色 \(c_i\)。对每个节点求以该节点为根的子树中出现的颜色种类数。
\(1\le n, c_i\le 2\times 10^5\)。
1.2S，125MB。

傻逼数据结构写多了就会和我一样一眼转换成 dfs 序做 HH 的项链、、、但是现在考虑 dsu on tree。

先考虑暴力要怎么做：大力枚举所有点再大力枚举其子树中的节点，用数组记录所有颜色出现次数维护颜色数即可，复杂度 \(O(n^2)\)，太烂了。发现暴力的问题在于重复统计了子树的信息。发现每个节点子树中颜色的出现情况包含了其所有子节点的子树与其本身，考虑能否重复利用子节点的信息来加速上述过程。

考虑预处理出每个节点子树大小与其重儿子，然后考虑 dfs 求解，过程中记 \(\operatorname{cnt}_i\) 表示颜色 \(i\) 的出现次数。从 1 开始向下遍历，遍历到节点 \(u\) 时，依次进行下列步骤：

  • 先遍历 \(u\) 的轻儿子并计算它们的答案，但不保留遍历后它对 \(\operatorname{cnt}\) 的影响。
  • 遍历 \(u\) 的重儿子，保留对 \(\operatorname{cnt}\) 的影响。
  • 加入 \(u\) 的贡献，再次遍历所有轻儿子的子树节点并加入贡献，并计算 \(u\) 的答案。
  • 若 \(u\) 是作为父节点的轻儿子被遍历的，则清空 \(u\) 的子树对 \(\operatorname{cnt}\) 的贡献后回溯，否则保留贡献直接回溯。

代码

U41492 树上数颜色

这题其实是给定了 \(m\) 次询问每次询问某个点子树的颜色种类数。按上述方法 dsu 预处理出所有节点的答案直接回答即可。

//知识点：dsu on tree
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 2e5 + 10;
const int kM = kN << 1;
//=============================================================
int n, a[kN];
int edgenum, head[kN], v[kM], ne[kM];
int dfnnum, node[kN], L[kN], R[kN], sz[kN], son[kN];
int nowans, ans[kN], cnt[kN];
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0'); 
  return f * w;
}
void Add(int u_, int v_) {
  v[++ edgenum] = v_;
  ne[edgenum] = head[u_];
  head[u_] = edgenum;
}
void add(int u_) {
  if (!cnt[a[u_]]) ++ nowans;
  ++ cnt[a[u_]];
}
void del(int u_) {
  -- cnt[a[u_]];
  if (!cnt[a[u_]]) -- nowans;
}
void Dfs1(int u_, int fa_) {
  L[u_] = ++ dfnnum;
  node[dfnnum] = u_;
  sz[u_] = 1;
  for (int i = head[u_]; i; i = ne[i]) {
    int v_ = v[i];
    if (v_ == fa_) continue;
    Dfs1(v_, u_);
    sz[u_] += sz[v_];
    if (sz[v_] > sz[son[u_]]) son[u_] = v_;
  }
  R[u_] = dfnnum;
}
void Dfs2(int u_, int fa_, bool son_) {
  for (int i = head[u_]; i; i = ne[i]) {
    int v_ = v[i];
    if (v_ == fa_ || v_ == son[u_]) continue;
    Dfs2(v_, u_, 0);
  }
  if (son[u_]) Dfs2(son[u_], u_, 1);
  for (int i = head[u_]; i; i = ne[i]) {
    int v_ = v[i];
    if (v_ == fa_ || v_ == son[u_]) continue;
    for (int j = L[v_]; j <= R[v_]; ++ j) add(node[j]);
  }
  add(u_);
  ans[u_] = nowans;
  if (!son_) {
    for (int i = L[u_]; i <= R[u_]; ++ i) {
      del(node[i]);
    }
  }
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  n = read();
  for (int i = 1; i < n; ++ i) {
    int u_ = read(), v_ = read();
    Add(u_, v_), Add(v_, u_);
  }
  for (int i = 1; i <= n; ++ i) a[i] = read();
  Dfs1(1, 1), Dfs2(1, 0, 0);
  
  int m = read();
  while (m --) {
    int u_ = read();
    printf("%d\n", ans[u_]);
  }
  return 0;
}

复杂度分析

时间复杂度 \(O(n\log n)\) 级别。

可以用类似重链剖分的方法来分析，详见：https://oi-wiki.org/graph/dsu-on-tree/#%E8%AF%81%E6%98%8E。

例题

CF570D Tree Requests

给定一个以 1 为根的 \(n\) 个结点的树，每个点上有一个小写字母，每个点的深度定义为该节点到 \(1\) 号结点路径上的点数。
给定 \(m\) 次询问，每次给定参数 \(a, b\) 查询以 \(a\) 为根的子树内深度为 \(b\) 的结点上的字母重新排列之后是否能构成回文串。
\(1\le n, m\le 5\times 10^5\)。
2S，250MB。

知识点：dsu on tree

一堆字符可以构成回文串，当且仅当出现次数为奇数的字符数量至多只有一个。判断回文串可以通过判断出现次数解决，于是考虑 dsu。

这题还有深度限制，于是在 dsu 的同时维护当前子树中，各深度的节点上所有字符的出现次数，在此过程中访问到对应节点时回答询问即可。

总复杂度 \(O(n\log n)\) 级别。

//知识点：dsu on tree
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
#define pr std::pair
#define mp std::make_pair
const int kN = 5e5 + 10;
const int kM = kN << 1;
//=============================================================
int n, m;
int edgenum, head[kN], v[kM], ne[kM];
int dfnnum, node[kN], L[kN], R[kN], sz[kN], dep[kN], son[kN];
int nowsum[kN], cnt[kN][26];
bool ans[kN];
char s[kN];
std::vector <pr <int, int> > q[kN]; 
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0'); 
  return f * w;
}
void Add(int u_, int v_) {
  v[++ edgenum] = v_;
  ne[edgenum] = head[u_];
  head[u_] = edgenum;
}
void add(int u_) {
  if (cnt[dep[u_]][s[u_] - 'a'] % 2 == 0) ++ nowsum[dep[u_]];
  else -- nowsum[dep[u_]];
  ++ cnt[dep[u_]][s[u_] - 'a'];
}
void del(int u_) {
  if (cnt[dep[u_]][s[u_] - 'a'] % 2 == 1) -- nowsum[dep[u_]];
  else ++ nowsum[dep[u_]];
  -- cnt[dep[u_]][s[u_] - 'a'];
}
void Dfs1(int u_, int fa_) {
  L[u_] = ++ dfnnum;
  node[dfnnum] = u_;
  sz[u_] = 1;
  dep[u_] = dep[fa_] + 1;
  for (int i = head[u_]; i; i = ne[i]) {
    int v_ = v[i];
    if (v_ == fa_) continue;
    Dfs1(v_, u_);
    sz[u_] += sz[v_];
    if (sz[v_] > sz[son[u_]]) son[u_] = v_;
  }
  R[u_] = dfnnum;
}
void Dfs2(int u_, int fa_, bool son_) {
  for (int i = head[u_]; i; i = ne[i]) {
    int v_ = v[i];
    if (v_ == fa_ || v_ == son[u_]) continue;
    Dfs2(v_, u_, 0);
  }
  if (son[u_]) Dfs2(son[u_], u_, 1);
  for (int i = head[u_]; i; i = ne[i]) {
    int v_ = v[i];
    if (v_ == fa_ || v_ == son[u_]) continue;
    for (int j = L[v_]; j <= R[v_]; ++ j) add(node[j]);
  }
  add(u_);
  for (auto x: q[u_]) ans[x.second] = (nowsum[x.first] <= 1);
  if (!son_) {
    for (int i = L[u_]; i <= R[u_]; ++ i) {
      del(node[i]);
    }
  }
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  n = read(), m = read();
  for (int i = 2; i <= n; ++ i) {
    int fa_ = read();
    Add(fa_, i);
  }
  scanf("%s", s + 1);
  for (int i = 1; i <= m; ++ i) {
    int u_ = read(), d_ = read();
    q[u_].push_back(mp(d_, i));  
  }
  Dfs1(1, 0), Dfs2(1, 0, 0);
  for (int i = 1; i <= m; ++ i) printf("%s\n", ans[i] ? "Yes" : "No");
  return 0;
}

CF600E Lomsat gelral

给定一棵 \(n\) 个节点的无根树，点有颜色 \(c_i\)，对于所有节点求在其子树中出现次数最多的颜色（可能不止一个）的编号之和。
\(1\le n\le 10^5\)，\(1\le c_i\le n\)。
2S，250MB。

知识点：dsu on tree，权值线段树

子树统计问题，考虑先套个 dsu。

发现如果只是用数组维护颜色的出现次数并记录当前出现次数最多的颜色编号之和，不容易处理删除操作。但是发现对这个数组的操作只有单点加/减和查询全体的众数，于是考虑用权值线段树维护各种出现次数的颜色编号之和，查询则在权值线段树上二分找到最右侧也即出现次数最多的位置即可。

总复杂度 \(O(n\log^2 n)\)。

//知识点：dsu on tree，权值线段树
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 2e5 + 10;
const int kM = kN << 1;
//=============================================================
int n, a[kN];
int edgenum, head[kN], v[kM], ne[kM];
int dfnnum, node[kN], L[kN], R[kN], sz[kN], son[kN];
int cnt[kN];
LL ans[kN];
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0'); 
  return f * w;
}
void Add(int u_, int v_) {
  v[++ edgenum] = v_;
  ne[edgenum] = head[u_];
  head[u_] = edgenum;
}
namespace Seg {
  #define ls (now_<<1)
  #define rs (now_<<1|1)
  #define mid ((L_+R_)>>1)
  const int kNode = kN << 2;
  LL t[kNode];
  void Pushup(int now_) {
    t[now_] = std::max(t[ls], t[rs]);
  }
  void Modify(int now_, int L_, int R_, int pos_, int val_) {
    if (L_ == R_) {
      t[now_] += val_;
      return ;
    }
    if (pos_ <= mid) Modify(ls, L_, mid, pos_, val_);
    if (pos_ > mid) Modify(rs, mid + 1, R_, pos_, val_);
    Pushup(now_);
  }
  LL Query(int now_, int L_, int R_) {
    if (L_ == R_) return t[now_];
    if (t[rs]) return Query(rs, mid + 1, R_);
    return Query(ls, L_, mid);
  }
  #undef ls
  #undef rs
  #undef mid
}
void add(int u_) {
  if (cnt[a[u_]]) Seg::Modify(1, 1, n, cnt[a[u_]], -a[u_]);
  ++ cnt[a[u_]];
  Seg::Modify(1, 1, n, cnt[a[u_]], a[u_]);
}
void del(int u_) {
  Seg::Modify(1, 1, n, cnt[a[u_]], -a[u_]);
  -- cnt[a[u_]];
  if (cnt[a[u_]]) Seg::Modify(1, 1, n, cnt[a[u_]], a[u_]);
}
void Dfs1(int u_, int fa_) {
  L[u_] = ++ dfnnum;
  node[dfnnum] = u_;
  sz[u_] = 1;
  for (int i = head[u_]; i; i = ne[i]) {
    int v_ = v[i];
    if (v_ == fa_) continue;
    Dfs1(v_, u_);
    sz[u_] += sz[v_];
    if (sz[v_] > sz[son[u_]]) son[u_] = v_;
  }
  R[u_] = dfnnum;
}
void Dfs2(int u_, int fa_, bool son_) {
  for (int i = head[u_]; i; i = ne[i]) {
    int v_ = v[i];
    if (v_ == fa_ || v_ == son[u_]) continue;
    Dfs2(v_, u_, 0);
  }
  if (son[u_]) Dfs2(son[u_], u_, 1);
  for (int i = head[u_]; i; i = ne[i]) {
    int v_ = v[i];
    if (v_ == fa_ || v_ == son[u_]) continue;
    for (int j = L[v_]; j <= R[v_]; ++ j) add(node[j]);
  }
  add(u_);
  ans[u_] = Seg::Query(1, 1, n);
  if (!son_) {
    for (int i = L[u_]; i <= R[u_]; ++ i) {
      del(node[i]);
    }
  }
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  n = read();
  for (int i = 1; i <= n; ++ i) a[i] = read();
  for (int i = 1; i < n; ++ i) {
    int u_ = read(), v_ = read();
    Add(u_, v_), Add(v_, u_);
  }
  Dfs1(1, 1), Dfs2(1, 0, 0);
  for (int i = 1; i <= n; ++ i) printf("%lld ", ans[i]);
  return 0;
}

CF1709E XOR Tree

给定一棵 \(n\) 个结点的无根树，点有点权 \(a_i\)，定义一棵树是合法的当且仅当树上所有简单路径的点权值异或和均不为 0。
现在可以把任意点的权值修改为任意正整数，求最少修改多少次可使给定的树合法。
\(1\le n\le 2\times 10^5\)，\(1\le a_i< 2^{30}\)。
3S，250MB。

知识点：dsu on tree

可以对权值修改为任意正整数，则修改某个节点后一定可以使经过该节点的所有简单路径权值和均不为 0，考虑什么节点需要被修改。

先钦定 1 为根，考虑 dfs 枚举简单路径的 \(\operatorname{lca}\)，若存在一条不经过已被修改的点，且 \(\operatorname{lca}\) 为枚举的点的异或和为 0 的路径，则该 \(\operatorname{lca}\) 一定要被修改。

记 \(\operatorname{dis}_i\) 为简单路径 \(1\rightarrow i\) 的异或和，则简单路径 \(u\leftrightarrow v\) 的权值异或和可以表示成 \(\operatorname{dis}_u\oplus \operatorname{dis}_v\oplus a_{\operatorname{lca}(u, v)}\)。则可以考虑在枚举 \(\operatorname{lca}\) 时使用 set 维护子树中节点的 \(\operatorname{dis}\)，在枚举子节点转移回溯后枚举子节点 set 中元素 \(\operatorname{dis}_t\)，检查当前点 set 中是否有 \(\operatorname{dis}_t\oplus a_u\)，若有则说明可以构成异或和为 0 的简单路径，该节点需要被修改，否则将枚举的元素插入到当前点的 set 中。

枚举完所有子节点后若该节点需要被修改则清空 set 并回溯，去除经过了被修改节点的路径的影响。

上述过程直接做复杂度上界是 \(O(n^2\log n)\) 的，但可以在合并 set 时启发式合并，若子节点的 set 更大则先交换父子的 set 即可，复杂度 \(O(n\log^2 n)\)。

不是那么板子的 dsu，但是思想完全一致，只不过因为此题中对答案有影响的并不是子树的全部节点而是子树 set 中维护的节点，所以启发式合并参考的对象由子树的大小变成了 set 的大小。

//知识点：dsu on tree
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 2e5 + 10;
const int kM = kN << 1;
//=============================================================
int n, a[kN];
int edgenum, head[kN], v[kM], ne[kM];
int nowans, ans;
int dis[kN];
std::set <int> s[kN];
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0'); 
  return f * w;
}
void Add(int u_, int v_) {
  v[++ edgenum] = v_;
  ne[edgenum] = head[u_];
  head[u_] = edgenum;
}
void Dfs(int u_, int fa_) {
  dis[u_] = dis[fa_] ^ a[u_];
  s[u_].insert(dis[u_]);
  int flag = 0;
  for (int i = head[u_]; i; i = ne[i]) {
    int v_ = v[i];
    if (v_ == fa_) continue;
    Dfs(v_, u_);
    if (s[u_].size() < s[v_].size()) std::swap(s[u_], s[v_]);
    for (auto x: s[v_]) flag |= (s[u_].count(a[u_] ^ x)) != 0;
    for (auto x: s[v_]) s[u_].insert(x);
  }
  if (flag) ++ ans, s[u_].clear();
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  n = read();
  for (int i = 1; i <= n; ++ i) a[i] = read();
  for (int i = 1; i < n; ++ i) {
    int u_ = read(), v_ = read();
    Add(u_, v_), Add(v_, u_);
  }
  Dfs(1, 0);
  printf("%d\n", ans);
  return 0;
}

写在最后

参考：

标签：int,dsu,tree,笔记,son,operatorname,节点
From： https://www.cnblogs.com/luckyblock/p/17984324

相关文章

  • 人工智能 第三版 第二章笔记
    人工智能第三版第二章笔记空间状态图状态空间图（state-spacegraph）是对问题的一种表示方法。其中有两种特殊类型的节点。其中一种是表示问题起始状态（startstate）的起始节点（startnode）。另一种特殊类型的节点对应于问题的终点或终止状态。问题的状态空间树包含了问题可能出现......
  • JAVA学习笔记--输出HelloWorld
    HelloWorld！写出人生第一个代码~随便新建一个文件夹用于存放代码新建一个Java文件新建一个名为Hello的txt文件或其他文本文件，将后缀名改为.java注意：如果系统没有显示文件后缀名，则需要手动打开在Hello.java文件中编写以下代码：publicclassHello{ publicstaticvoi......
  • JAVA学习笔记--JDK安装及环境变量配置
    Java开发环境搭建卸载JDK找到JDK的安装路径，删除JDK的整个文件夹删除JAVA_HOME(右击我的电脑-->属性-->高级系统设置-->环境变量，即可找到JAVA_HOME)删除path下关于java的目录在终端输入java-version，若显示'java'不是内部或外部命令，也不是可运行程序或批处理文件，则成......
  • JAVA学习笔记--常见的Dos命令
    基本的Dos命令打开cmd的方法以管理员的身份打开：开始--->命令提示符（Win11）Win键+R-->输入cmd打开控制台（推荐使用）在任意文件夹下，按住shift键+鼠标右键点击，在此处打开命令行窗口资源管理器的地址栏前面加上cmd路径(注意：cmd后有空格)常见的Dos命令##盘符切换输入想要切换到......
  • xtuner微调大模型笔记
    微调原理想象一下，你有一个超大的玩具，现在你想改造这个超大的玩具。但是，对整个玩具进行全面的改动会非常昂贵。※因此，你找到了一种叫 LoRA 的方法：只对玩具中的某些零件进行改动，而不是对整个玩具进行全面改动。※而 QLoRA 是LoRA的一种改进：如果你手里只有一把生锈的螺丝刀，也......
  • 优美的暴力——树上启发式合并（dsu on tree）
    dsuontree前言在我认为，这个并不能说单独列出来成为一个算法，更恰当的说，是一种思想、技巧。反正挺简单的，也很有趣（谁会拒绝一个优美的暴力呢），所以写篇笔记记录一手。dsu是什么dsu一般指“disjointsetunion”，即并查集。那么dsuontree也就是指树上的合并和查询操作。但是......
  • 2024/1/23 算法笔记
    1.负进制数[P1017NOIP2000提高组]进制转换-洛谷|计算机科学教育新生态(luogu.com.cn)所谓负进制数，就是进制数为负数的一种实数表示法。例如，-15(十进制)相当于110001(-2进制),并且它可以被表示为2的幂级数的和数:110001=1(-2)5+1*(-2)4+0(-2)3+0*(-2)2+0(-2)^1+1(-2)......
  • 大三寒假学习进度笔记14
    今天在编写项目时了解到了PyTorch3D这个库，因此对这个库进行了一定的了解并尝试使用这个库PyTorch3D旨在与深度学习方法稳定集成，以预测和处理3D数据。在进行安装PyTorch3D时产生了很多错误。在anaconda虚拟环境使用condainstall下载PyTorch3D时总是会卡在solvingenvironment这......
  • 卷积神经网络学习笔记
    全连接神经网络的结构全连接神经网络的整体结构可以简化为智能函数\(y=f_θ(x)\)输入和输出层一般为数据矩阵全连接网络的单元结构神经网络的思路：从单元到整体一个单元的结构：\(X_1,X_2,X_3...\)是很多矩阵，然后这些矩阵分别乘上对应的权重矩阵，再加上偏置矩阵b，输......
  • Binary tree traversal-- beadth-first and depth-first【1月23日学习笔记】
    点击查看代码//Binarytreetraversal--beadth-firstanddepth-first#include<iostream>#include<queue>//STLusingnamespacestd;structnode{intdata;node*left,*right;};node*getnewnode(intx){node*temp=newnode;temp-&......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99