DSU
DSU on tree 学习笔记
DSU on tree 通常用来解决不带修树上子树问题。 主要思想： 剖分。 先搜轻儿子，记录轻儿子子树的答案，删去轻儿子的贡献。 搜重儿子，记录重儿子子树的答案，保留重儿子的贡献。 回溯，重新搜轻儿子，把轻儿子子树的贡献加上，构成本子树的答案。 CF600E Lomsat gelral #incl ......
【模板】树上启发式合并 dsu on tree
所选例题 模板 点击查看代码 #include<bits/stdc++.h> using namespace std; #define endl '\n' #define pb push_back #define rep(i,a,n) for(int i=a;i<=n;i++) #define pe ......
树上启发式合并（dsu on tree）
dsu on Tree(树上启发式合并) 当遇到处理子树询问，并且无修改时。可以考虑树上启发式合并。 算法流程： step1：处理出每个点的 \(siz_x\) 以及重儿子 \(son_x\)。 void dfs(int x, int fa) { siz[x] = 1; int Maxson = 0 ......
启发式合并,DSU on Tree
启发式合并,DSU on Tree 一、启发式合并 1.1传统启发式合并 启发式合并是做的一个什么事情？ 给你\(n\)个集合，令\(s_i = \lbrace i\rbrace\) 选两个集合\(x,y\),把\(y\)里面的元素全部丢到\(x\)里面，令\(s_x = s_x\cup s_y\) ......
【学习笔记】DSU on Tree
## 概述 DSU on Tree 即树上启发式合并，重点不在“合并”，而在利用树链剖分的性质对子树问题进行复杂度正确的分治。 ## 算法流程 1. 递归处理轻儿子的答案 1. 递归处理重儿子的答案 1. 重新遍历轻儿子子树，计算当前子树的答案 1. 如果当前节点是轻儿子，重新遍历整棵子树，清除答案 ......
【大联盟】20230626 集查并（dsu） 题解 AT_toyota2023spring_final_g 【Git Gud】
【大联盟】20230626 集查并（dsu） 题解 AT_toyota2023spring_final_g 【Git Gud】 zyx /bx ## 题目描述 [here](https://atcoder.jp/contests/toyota2023spring-final/tasks/toyota ......
dsu-on-tree-浅谈
title: dsu on tree 浅谈 feature: false mathjax: true preview: date: 2022-08-01 21:30:14 tags: - dsu on tree categories: 算法 cover: https://pic.imgdb.cn/i ......
[学习笔记] 启发式合并 & DSU on Tree
# 一、启发式合并 启发式合并多用于合并两个集合，现在有这样一个问题： 现在给定 $n$ 个集合，第 $i$ 个集合初始只有 $\{i\}$，要支持集合的合并操作。 如果我们暴力合并，时间复杂度会是 $O(n^2)$ 的。 参考并查集的按秩合并，考虑将小的集合合并到大的集合上。 考虑计算时间复杂度， ......
dsu on tree 学习笔记
# dsu on tree 学习笔记 ## 引入 dsu 是并查集的缩写，然鹅本算法和并查集没啥关系。当然，dsu on tree 也有中文名字：树上启发式合并。也就是说，这个算法是用于处理一些树上信息的合并的。 dsu on tree 和莫队一样，都是优雅的暴力。优雅是因为思想很优雅，暴力是因为所 ......
DSU on tree
DSU on Tree DSU on Tree 是指在树上利用类似于并查集的启发式合并的方法处理一类统计的问题。比如这些问题：对于每一个子树T，计算： 1）T中结点的值组成的众数 2）T中不同的结点的值的个数 3）T结点的值从小到大排序后最接近T的根结点的值 以子树中不同的结点的值的个数为例，如果直 ......
DSU on tree——从入门到入土
# DSU on tree——从入门到入土 [TOC] ## 1.dsu有什么用？ ### 降低时间复杂度——nlogn dsu的作用在于将时间复杂度降低，由n方到nlogn 举个例子： 给一棵根为1的树，每次询问某个子树内颜色有多少种。树有N个节点，询问有M次。颜色范围为 [1,N]的整数。 数据 ......
[学习笔记] dsu on tree
- 适用于动态维护子树信息 - 流程 类似树链剖分定义重儿子，轻重链。 先便历轻边子树，不保存信息（删）。 最后便历重儿子子树，保存重儿子信息。 再加入轻儿子子树即可得到子树信息了。 复杂度：一个点被加/删的次数为轻边数( $logn$ )。 - code 点击查看代码 ``` void solve ......
树上启发式合并（dsu on tree）
解决树上询问问题，没有修改 时间复杂度：$O(nlogn)$ 例题：https://codeforc.es/contest/600/problem/E 题意：给定一颗树，每个节点有一个颜色，求出子树中颜色最多的颜色值之和。 代码： #include<bits/stdc++.h> using name ......