点分树（动态点分治）
点分治的核心思想在于依据重心划分子连通块，其良好的性质保证了最多只会分治 logn 层。有了这一特性，便可使用各种暴力计算答案。那么我们按照分治递归的顺序提一颗新树出来，易知树高是 O(logn)的，称之为点分树。
具体的性质，在博客中有完整的阐述。概括如下：
- **点 x 在点分树上的子孙集合就是原树中以 x 为重心（分治中心）时的分治区域，点分树上所有点的子树大小之和为 O(nlogn) **（每个点会被从根到它的路径上最多 logn 个祖先所统计）。这意味着，即便在每个节点上保存所有子孙的信息，空间复杂度只是O(nlogn)的。
- 点分树的树高为 O(logn)。这意味着，如果要对某个点进行修改操作，直接在点分树上暴力跳父亲，改变 O(logn) 个祖先的子树信息即可。统计亦同理。
- 对于点分树上 x 与 y 的 lca（或者说囊括连通块同时包含 x,y 的所有点分树节点中深度最深的那一个），易知在以此点为重心划分子连通块时 x,y 会首次被分割开来，因此该点必定在原树的 x,y 路径上。我们采集y对x的贡献，仅需从该lca上读取信息。
- 点分树的一个子树总是原树上的一个联通块。在点分治过程中到达点u时，u的子节点数量在原树（当前树以u为根，除去已被标记的点）和点分树上是相同的，且一一对应，即，u在原树的不同儿子处在不同次级分治区域中内，获取来自某一儿子的信息，相当于获取来自对应的点分树子节点的信息。
- 节点x的分治区域被包含在y中，当且仅当y是x的祖先，也就是说，只有x的祖先记录了以x为终点的链，x的子孙节点的分治区域中不包含x，而其余的节点的分治区域则与x独立。点分树上，各分治重心所负责的路径互不重复。
点分树的每个节点u，都可以看作是这样一棵树，它包含u的分治区域，并以分治重心u为根，负责统计（部分）经过u的路径。与根直接相连的各个子树，就是u的点分树子节点的分治区域。当一个点、一条边被修改，影响的是这棵树中的某一子树（联想DFS序），我们可以建立数据结构来维护这棵以u为根的树。
点分树的常数相当大，\(O(n(logn)^2)\)的复杂度甚至往往只能应付1e5而不能应付2e5，所以除了要细心降低常数外，我们在一个点分树节点上套数据结构时也得慎之又慎。由于每个节点所代表的分治区域大小总和不超过nlogn，我们在一个点分树节点上套数据结构，可以该结构的大小设置为以此节点为分治中心时的连通块大小（一般得再多预留一点空间）。
特别地，如果边权为1，那么从某一节点出发到其分治区域的任一点的链长，都不会超过连通块大小，我们可以使用静态表vector来O(1)地记录与读取某一长度的链的信息，而不是用map。考虑到连通块内的点数同样有限，我们可以在vector下再套vector来存放点编号，这都是允许的。
点分树和原树在结构上关联甚小，一定不要认为点分树上相邻节点在原树上也是相邻的。
能解决什么问题？
通常而言，点分树是一种维护端点链的工具，在具体问题中可以灵活运用。
一类典型的题目就是，指定树上一点，求与此点的路径长度满足一定条件的其他所有点的贡献之和，在需要时还得支持在线和带修。对于点分树节点u所代表的连通块中每个节点v（在进入这个连通块时，u为根），将端点链u-v的信息、贡献保存在u中（记作F1[u]），可以保证所有节点保存的链都是独立的，且可以组成树上的所有路径。对于指定的原树点x，以x为端点的路径，一定只能从“x到x在点分树上的祖先（含x本身） + 该祖先所记录的某条不位于x所在的子连通块的链（含该祖先单独本点，这经常被忽略）”组成（注意切勿把x在点分树的祖先与原树的祖先混淆）。假设v是u的子节点（点分树上），将v所代表的连通块（含有x）的所有点对v的父亲（这是确定且唯一的）的贡献保存在v中（记作F2[v]），在对x求解时额外减去这些贡献即可。
可以通过O(1)求LCA的方式来节省求两点路径的logn开销（题外话，树剖在一般情况下能与ST表不分上下）。不过考虑到我们一般只求点分树上节点到其祖先的距离，而祖先数量又不超过logn，我们可以对点分树执行一次预处理达到同样的效果。
long long query(x) //这是个大致模式参考
{
long long res=F1[x];
for(int y=x;fa[y];y=fa[y])
{
long long d=dis(x,fa[y]); //原树上的路径的距离，这个信息在很多题目要用到
res+=F1[fa[y]]-F2[y];
}
return res;
}
点分树是对点分治过程的实质化，不难发现，点分治过程就是在这棵树上的DFS。
P2056] 捉迷藏 在点分树上，节点x的信息只保存在其祖先节点中，x受到改动也只会影响的祖先记录的结果，于是修改其祖先的信息、重新更新祖先的结果，并维护全局答案即可。对于x的某个祖先y，其记录的是在以y为根的分治区域树中，经过y的最长路径，因此它只在意各个子树的最长链，我们可以用multiset来维护。点分树中所有节点所记录的结果的最大值，就是全局解，我们还是用multiset来维护这n个分治重心的结果，当一个分治重心的结果改变时，重新维护全局解。
同样的，从点分树根节点到某一节点的决策路径，也可以看做是不断细分的过程，类比二分，这适用于一些有单调性质的问题。比如说越靠近某一个靶点，点值会越大/越小。具体地讲，我们确定目标节点一定在原树某一个连通块内，根据“点分树的一个子树总是原树上的一个联通块”这一重要性质，我们从点分树根节点出发，一路向下，不断地缩小连通块（如果原树中u的子节点v更优，可移动到v所在的连通块），最终就能找到靶点。
以P3345]幻想乡战略游戏为例：
ll sea(int x)//传至此节点的点权和以及总贡献
{
ll me=query(x);
int vn=G[x].size();
for(int i=0;i<vn;++i)
{//在原图上做决策，在点分树上做移动
if(query(G[x][i].first)<me) //本题（求点带权重心）的性质：非重心的节点，至少有一个邻节点的值小于自己
return sea(Gx[x][i]); //我们在建树时，x在原树的每个邻节点恰好对应x在点分树的子节点，从而可以快速找到该邻节点所在的连通块的重心
//由于单调性，一定不会回到x在点分树的父节点
}
return me;
}
那么我们在建树时，可以——
for(int i:G[x]) //遍历邻点
{
if(vis[i])
{
Gx[x].push_back(i); //x在点分树的父节点
continue;
}
tot=sz[i];
rt=0;
get_root(i,0);
Gx[x].push_back(rt);
}
原文地址：http://www.cnblogs.com/blover/p/16815969.html
