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

前面所提到与树有关的数据结构，大部分都是在一棵树上进行的。如果是在森林中连边和删边，就要使用LCT了。LCT可以看作是树链剖分与Splay树的组合，建模中用到了树链剖分，但实际写起来与树链剖分没什么关系，主要用Splay树。它的平摊时间复杂度为\(\mathcal{O}(\logN)\)。1LCT

一些前言每次做树剖时打开题解...使用LCT简单维护即可。内心：？？？code好√8短啊又很奇怪有种不知道却又高端大气的感觉这次来说清楚LCT到底是个什么东东问题引入例题传送门有一棵树，需要支持操作：修改节点\(u\tov\)路径值查询节点\(u\tov\)路径值很明显，这是

因为白点对\(f_i\)没有贡献，所以可以重构出一棵原树的子树，使得所有的叶子都为标记点且标记点数量不变（没有删去标记点）。因为没有标记被删去且结构不变，所以这棵树的答案与原树答案相同。现在，对于所有节点，到它距离最大的标记点一定在叶子上。那么问题就变为：求出树上任意一点到所有

T1新的阶乘有三种做法，第一种也就是我写的这种容易被评测机波动坑，复杂度玄学考虑处理出每个数的质因数，然后就暴力除每个数的质因数的种类次非常的简单，也容易被卡第二种是与第一种差距不大，就是在线性筛中处理出质因数之后，再对每个数除以线筛中处理的质因数，将它的答案加到除数和

前置芝士：SplayLCT(Link-CutTree)使用场景：动态树问题。基本概念：原树：给定的原始树。实边：在原树中节点\(cur\)选取一个子节点\(son\)，则\(cur-son\)的连边为实边。虚边：不是实边。实链：由实边构成的链。基本思想:将原树中的一条链，用一颗平衡树（一般是Splay）来维护，其中

题目链接2539.动态树给定\(n\)个点，编号从\(1\)到\(n\)，其中第\(i\)个点的初始权值为\(a\_i\)。现在要对这些点进行\(m\)次操作，操作共分为以下\(4\)种：0x

CF1329C不难发现，在最终的树中，叶子肯定是在原树的子树中最小的那个。而其他节点是原树的子树中大于两个叶子的最小的点，类似归并排序的做即可，偷懒写了个启发式合并。code