专业的网站建站公司,网站内容采编怎么做,网络服务商是谁,自助商城0.引言
对于树上问题#xff0c;有许多特殊的求解方法#xff0c;如#xff1a;树链剖分。点分治算法也是其中之一#xff0c;常用于解决树上路径问题。
1.0.问题的引入
给定一棵树#xff0c;求这棵树的直径#xff08;树上最长链长度#xff0c;n10^5#xff…0.引言
对于树上问题有许多特殊的求解方法如树链剖分。点分治算法也是其中之一常用于解决树上路径问题。
1.0.问题的引入
给定一棵树求这棵树的直径树上最长链长度n10^5
解法1.两遍dfs先任选一个起点t通过dfs遍历整个树找到最长路的终点v再从v进行dfs第二次dfs找到节点u树的直径即为u-v的路径长度。此非本文内容证明不再撰述。
解法2.暴力点分治
首先考虑枚举算法对于一个节点u我们可以先枚举所有经过u的链的长度s。
对于一个u的子树T记f[T]Maxdistu,vv∈T。
显然f[T]max(f[A])1A是T的子树。
则sMaxf[T]Maxf[ T ]1T≠T。
也就是说s为子树中最远点v1与次远v2点的距离且v1v2不在同一个子树内是即为经过u的最大链长度。
于是我们可以求出u的每个子树的最远点距离将最大和次大距离相加即是s。
此时发现答案中与u有关的部分都求解完毕只需要分治求解u的子树的s最后合并答案即可。 这暴力枚举算法的时间复杂度是多少呢
显然这个算法的时间复杂度为Osigmasize的也就是所有节点的子树大小之和。
发现这个算法在 数据退化为一条链的情况下时间复杂度为On^2。 如何优化
我们需要尽量保持树的平衡那么我们当然选择将子树的“重心”作为子树的根。
(重心找到一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心)
我们发现选取重心之后分治树节点u的每个子树大小一定小于u树的大小的一半。
于是时间复杂度为O(n log n)且有时根本达不到n log n的时间。 一般有两种合并方式
1.子树依次合并统计答案。
2.求出所有链的答案再减去不包含这个节点的答案。 完美
1.1.点分治的实现
void get_center(int u,int father,int Size) //Size表示整棵树的大小
{tree[u]{1,0}; //u节点初始化 for (int ihead[u];i;ie[i].next){int ve[i].to;if (size[v]||vfather) continue;get_center(v,u,Size); //dfstree[u].sizetree[v].size; //更新u子树大小 tree[u].heavy_songet_max(tree[u].heavy_son,tree[v].size); //更新u的子树的最大值 }tree[u].heavy_songet_max(tree[u].heavy_son,Size-tree[u].size); if (tree[u].heavy_sonMIN) {rootu,MINtree[u].heavy_son};
}
void divide(int u)
{anssolve(u,0),visit[u]1; //求所有链的答案 for (int ihead[u];i;ie[i].next) {int ve[i].to;if (visit[v]) continue;ans-solve(v,e[i].d); //减去不经过u的答案 Smersize[v];root0;MININF; get_center(v,0); divide(v);}
}
