只能基础查询到根节点的距离structDSU{intfa[N],siz[N],deep[N];voidinit(){for(inti=1;i<=n;i++){fa[i]=i;siz[i]=1;deep[i]=0;}}intfind(intx){inttmpfa=fa[x];

0829-T4太空帝国题意给定一个图有\(n\)个点，每个点的坐标为\((x_i,y_i,z_i)\)。点\(i\)和点\(j\)的距离为\(\min(|x_i-x_j|,|y_i-y_j|,|z_i-z_j|)\)。求该图的最小生成树。思路暴力建图不能通过。对最小生成树有贡献的边只可能连在按\(x\)或\(y\)或\(z\)排序

P9992[YnoiEasyRound2024]TEST_130之前大概想出来了，但是没想清楚。发现每次询问\(w,d\)就相当于算\(w\)子树里离\(w\)距离不超过\(d\)的点的贡献之和，\(w\)的贡献是\(d+1\)（因为\(N(w,0),N(w,1),\ldots,N(w,d)\)都可以），\(w\)往下第一层的每个点分别的贡

参考文章：树上启发式合并[dsuontree]树上启发式合并总结树上启发式合并の详解启发式合并启发式算法是什么呢？启发式算法是基于人类的经验和直观感觉，对一些算法的优化。举个例子，最常见的就是并查集的启发式合并了，代码是这样的：voidmerge(intx,inty){intxx=find(x

【题解】SolutionSet-NOIP2024集训Day12树上启发式合并https://www.becoder.com.cn/contest/5472「CF600E」Lomsatgelral直接dsuontree。记录每一个颜色的出现次数。「IOI2011」Race之前是用点分治做的。考虑dsuontree。每个子树内维护到根节点的距离为\(x\)

树分治这部分知识是我的弱项，之前学习时也没有听懂。此前碰到这类题也会想尽办法用数据结构代替，但发现非常不可做，代码复杂程度极高。而且感觉之前我连普通的区间分治都不太熟练，没有学好的信心。现在学习过后好了很多，理解了分治的核心（也许），就是每次到分治的关键点就去统计包含关键点

关于迟到这么多天就迟到一次就被抓了个正着/jk今天刚好错过地铁，后来在地铁上碰见了int08，本来他和我都坐的上一班结果今天都迟到了，然后在路上就一直讨论李老和hfu抓住我们的概率。本来我想今天迟到就算了，毕竟刚好错过地铁下一班要等好一会没办法，但int08认为他有很大概率被抓

StampRallykruskal重构树板子，套上二分求一下祖先即可。AND-MEXWalk注意到答案只可能是0,1,2。因为1和2显然不能同时存在。证明：可知边权序列不增，如果前面出现2则说明第1位是0，由于是与运算所以不可能有1了。判断0和1即可。0好判断，只要全不为0，也就是最后

关于冰茶姬简述冰茶姬是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。顾名思义，冰茶姬支持两种操作：合并（Union）：合并两个元素所属集合（合并对应的树）查询（Find）：查询某个元素所属集合（查询对应的树的根节点），这可以用于

前置知识:树链剖分的一些东西会打暴力DSUOnTree是啥中文名:树上启发式合并/静态链分治先考虑启发式合并是啥:说到启发式合并，那么常见的就是并查集了。我们将小的集合合并到大的集合中，就可以变成\(O(n\logn)\)神奇让高度小的树成为高度较大的树的子树，这个优化可

dsuontree模板运用例题以及代码：U41492树上数颜色-洛谷|计算机科学教育新生态(luogu.com.cn)记录详情-洛谷|计算机科学教育新生态(luogu.com.cn)Lomsatgelral-洛谷|计算机科学教育新生态(luogu.com.cn)记录详情-洛谷|计算机科学教育新生态(luogu.com.

CL-21一般拿到这个题第一眼都应该能看出并查集，subtask1是给并查集暴力修改的.后面subtask2没有联通操作，是给纯线段树的，也算是启发正解了再往下可以考虑操作\(1\)采用线段树区间修改，操作\(2\)采用并查集维护的思路.按这个思路去想，那么操作\(2\)肯定不能进行修改，因为我

数据结构——并查集学习笔记并查集是一种用于管理元素所属集合的数据结构，实现为一个森林。并查集中，每棵树表示一个集合，树中的节点表示对应集合中的元素。其思想是，把集合属性绑定到根节点上，避免多余的处理，因此一般难以分离。普通并查集并查集支持两种操作：合并（Union）：合并两个元素

给定N条直线、M组位置关系(平行或垂直)和Q个查询，要求输出共有多少组平行线，并回答询问的直线之间的位置关系。提示：种类并查集。#include<bits/stdc++.h>usingi64=longlong;structDSU{std::vector<int>f;DSU(intn){init(n);}voidinit(

E-CliqueConnecthttps://atcoder.jp/contests/abc352/tasks/abc352_e最小生成树先复习一下最小生成树，这里用Kruscal生成树（spanningtree）：一个连通无向图的生成子图，同时要求是树。也即在图的边集中选择\(n-1\)条，将所有顶点连通。最小生成（MinimumSpanningTree，MST）：边

从启发式合并到DsuonTree传统启发式合并[HNOI2009]梦幻布丁题目描述\(n\)个布丁摆成一行，进行\(m\)次操作。每次将某个颜色的布丁全部变成另一种颜色的，然后再询问当前一共有多少段颜色。例如，颜色分别为\(1,2,2,1\)的四个布丁一共有\(3\)段颜色.输入格式第一行是两

有人说，直接点分树，力大砖飞，非常不错！实际上这种做法非常的垃圾，很多时候我们使用点分树，一定是不得不使用点分树，比如模板题，强制在线，非常的恶心，所以我们使用点分树。而点分树是否必要呢？既然你能看到这篇blog，他肯定是不必要的！我们今天来发掘dsuontree的美妙性质，让他求解这个问题！然

VP的。猜猜为啥没有penalty？因为T的没有测完。submissionsA,B直接暴力。C一个很简单的方法就是第\(i\)次把\(i\)放到应该在的位置。当然如果原先就在了就别管。D一个联通图中的每两个点都能成为朋友。因此直接dsu。E记忆化搜索。注意到如果投骰子投到\(1\)，直接

主要思想是树的重轻儿子之分使得时间复杂度为o(nlogn),神奇欲深入了解的这里:https://oi-wiki.org/graph/dsu-on-tree/点击查看代码#include<bits/stdc++.h>usingnamespacestd;typedefstructedge//边结构体{intto,next;}EDGE;//边相关数组EDGEe[100001<<1];

今天模拟赛T2用到了，所以来浅浅地学一下DSUontree。对于一类树上问题（大多是和路径有关的），其暴力复杂度通常会带上一个\(n^{2}\)，这时利用启发式合并就可以将其优化到\(n\logn\)。具体地，假设搜索到了\(u\)结点，令\(son_{u}\)表示结点\(u\)的重儿子，那么：先对\(u\)的

树上启发式合并适用于维护子树内信息例题：CF246E思路暴力将询问离线下来，挂在每个点上对于每个点\(x\)，维护一个桶\(cnt_{dep}\)，统计深度\(dep\)下不同字符串出现的次数对于\(x\)上的询问输出\(cnt_{dep_x+k}\)每切换一个\(x\)，\(cnt\)要重置\(DSU\)优化维护

在地铁上口胡了一下。不知道对不对。考虑记录每一个点\(i\)离他最远的一个祖先使得祖先到\(i\)的路径上没有\(a_i\)。设他为\(\text{lst}_i\)。然后如果两个\(u,v\)的\(\text{lst}\)相等，那么这条路径就是好的。每种颜色枚举即可。八成假了（？），欢迎Hack。PS：全对了，确实能

题意给定一棵树，求区间\([l,r]\)中任意两点的LCA的不同的带权深度的个数。Sol很容易想到Dsuontree。因为当前点\(x\)作为LCA产生贡献当且仅当有两点\(u,v\)分别在\(x\)的不同子树中。集中注意力，不难发现对于一个\(u\)来说，只有子树中她在序列上的前驱后继会

https://www.luogu.com.cn/problem/CF1702E转化题意把所有数连边，判断是否为二分图。染色法voidsolve(){#definetestsintn;std::cin>>n;std::map<int,std::vector<int>>edge;std::vector<bool>used(n+1);boolok(true);