实在拖得太久了。
先扔掉资料
http://www.cnblogs.com/qt666/p/6597276.html
http://www.cnblogs.com/nietzsche-oier/p/6604245.html
http://blog.csdn.net/jiangshibiao/article/details/25738041?utm_source=tuicool&utm_medium=referral
http://blog.csdn.net/ALPS233/article/details/51398629
http://blog.csdn.net/vecsun/article/details/52808502
http://www.cnblogs.com/fullpower/p/3869547.html
分治的核心是尽量把一个整体分成接近的两个部分，这样递归处理可以让复杂度从n²变成nlogn。
两个问题，如何区分和如何算答案。
对于第一个问题，重心，然后就是找重心的方法，两个dfs，
对于第二个问题，对于每个重心算当前块中每个点到重心的答案，然后由重心分开的块要把多余的信息去掉。
求出重心的两个dfs
第一，先算出每个点的子树大小
void dfs_size(int x,int fa) { size[x]=1; repedge(i,x) { int too=e[i].toward; if (!vis[too] && too!=fa) { dfs_size(too,x); size[x]+=size[too]; } } }
第二，如果把一个点作为重心，它会把当前的联通块分成两个部分，子树和整个联通段的大小-子树，通过第二个dfs找到一个可以把图分成两快大小平衡的连通图
void dfs_find(int x,int fa,int y) { // printf("%d %d %d %d ",x,fa,y,sz[x]); msz[x]=y-sz[x]; repedge(i,x) { int too=e[i].toward; if (!vis[too] && too!=fa) { dfs_find(too,x,y); msz[x]=max(msz[x],sz[too]); } } if (msz[root]>msz[x]) root=x; }
//这里把root开成全局变量
统计答案的more函数和dfs下去的calc函数
more函数用于计算答案，当需要维护动态信息是，more函数用于一开始构建节点保存数据结构的初始化。
LL more(int x,int len) { memset(num,0,sizeof(num)); dfs_len(x,0,len); LL sum=0;
/×计算过程×/return sum; }//update
calc函数用于不断递归下去就子树
void calc(int x) { int root; dfs_size(x,0); root=dfs_root(x,0,size[x]); ans+=more(root,0); // 加入答案 vis[root]=1; repedge(i,root) { int too=e[i].toward; if (!vis[too]) { ans-=more(too,e[i].v); //减点不合法的答案，就是在同一棵子树上的 calc(too); } } }
如果子树的信息无法通过more直接减掉，可以分开写calc和more
，即
void calc(int x) { dfs_size(x,0); root=0; dfs_find(x,0,sz[x]); vis[root]=1; repedge(i,root) { int too=e[i].toward; if (!vis[too]) { more(too,0,num[too],num[root]); /×计算×/ } } repedge(i,root) { int too=e[i].toward; if (!vis[too]) calc(too); } }
附上点分治会用上的dfs_len函数，用于记录长度信息
void dfs_len(int x,int fa,int len) { d[++tot]=len; repedge(i,x) { int too=e[i].toward; if (!vis[too] && too!=fa) dfs_len(too,x,len+e[i].v); } }
对于动态点分治，也是由点分治引出来的，显然对于一个点，他最多属于logn个重心所在的块，重心之间又是有层次关系，可以抽象构造一个重心树，用数据结构就可以啦。
比较麻烦的在于对于重心带的数据结构，他的域要控制得和这个块大小差不多，很多人用vec动态申请空间当bit用，我习惯用线段树。
难点跟点分治一样，在于剔除在同一棵子树上的重复信息，所以要构建两个数据结构，一个做加的，一个做减的
构建完后，对于询问或修改的某个点，依次访问它从里到外每个重心的统计信息。