前言还真没有。点分树点分树是个神秘的东西。点分树是通过更改原树形态使树的层数变为稳定\(\logn\)的一种重构树。常用于解决与树原形态无关的带修改问题。是这样的，有些树上问题，看起来用别的树形结构做不了，点分治能做。但是它不仅多次询问（\(n\)同级），还带修，有时候甚至

//【模板】点分树|震波//https://www.luogu.com.cn/problem/P6329#include<bits/stdc++.h>#definedebug(a)cerr<<"Line:"<<__LINE__<<""#a<<endl#defineprint(a)cerr<<#a"="<<(a)<<endl#d

1.定义在点分治的基础上加以变化，构造一颗支持快速修改的重构树，称之为点分树2.算法2.1.思路点分治的核心在于通过树的重心来划分联通块，减少合并层数，从而降低时间复杂度所以，我们可以按分治递归的顺序提出一颗树，易知树高至多为logn具体的说，对于每一个找到的重心，将上一次分治

点分树是一个处理树上距离的优秀DS。它可以快速处理关于一些树上距离问题。引入我们知道，我们在做点分治的时候，每次找到中心，然后将重心所有的相连的边断开，处理子问题。时间复杂度是\(O(n\logn)\)的。但是有些题目让我们搞强制在线，又要求距离为\(k\)的所有和，这时候点分树

structBIT{ intsz; vector<int>c; voidbuild(ints){ c.resize(s+1); sz=s; } intlowbit(intx){ returnx&(-x); } voidadd(intx,inty){ x++; for(;x<=sz;x+=lowbit(x))c[x]+=y; } intsum(intx){ x++; intans=0;x=min(x,sz)

感觉可以理解为带修点分治。常用于解决与树原形态无关的带修改问题。——oi-wiki点分树是通过更改原树形态使树的层数变为稳定\(\logn\)的一种重构树。就是通过点分治找重心的方式，将这一层重心为上一层重心的儿子。所以对于很多暴力的复杂度是正确的。一开始发现建树错了

模板题题目传送门给定一棵树（带点权），支持以下操作：修改点权。查询到一个点距离\(\lek\)的点的权值和。\(n,T\le10^5\)算法解析前置知识：点分治我们考虑把每次求出的重心和上一层的重心连边，我们就可以得到点分树。这棵树有以下性质：树高为\(\logn\)，也就是暴力找LCA的

氡态淀粉质or淀粉素产品用途本章讲解本产品的用途，即大规模处理带修改的树上路径。本产品是点分治的进阶版，故而又名“动态点分治算法”。使用方法前置芝士点分治，请看上一篇博客。点分治利用了重心的特质，使得分治不会超过\(\log{n}\)层。这一点不论过去还是现在都很重要（用

一种用来解决一类与树的形态无关的问题。首先需要知道点分治。然后点分树就是把点分治过程变成一棵重构树。一个点的儿子就是下一层分治中选择的重心。容易发现点分树的

黄昏夕阳，铺一片余晖锦缎，远处炊烟袅袅，我们活在这美好温暖的人间。本文是基于辰星凌的博客QAQ大佬的博客的自己的一些“摘抄”和自己的一些想法点分治的核心思想在于依据

点分树（动态点分治）点分治的核心思想在于依据重心划分子连通块，其良好的性质保证了最多只会分治logn层。有了这一特性，便可使用各种暴力计算答案。那么我们按照分治递归的

今天又是考试改不动了才发现std::chrono::system_clock::now().time_since_epoch().count()时间是精确到纳秒的啊（后知后觉我突然在想啊你看不是有一些毒瘤