1. 什么是树分治树分治Tree Divide and Conquer是一种基于分治思想处理树形结构问题的算法范式。它将树分解为若干规模更小的子树分别解决子问题后再合并结果从而高效解决树上的路径统计、最值查询、动态规划等问题。2. 树分治的核心思想树分治的核心在于如何将树分而治之。主要有两种经典策略点分治每次选择树的重心作为分割点将原树分解为若干互不连通的子树保证子问题规模均衡。边分治选择一条边将树分成两个连通块递归处理两个子树。其中点分治更为常用因为它能保证递归深度为 O(log n)而边分治在菊花图中可能退化为 O(n)。3. 点分治算法框架点分治的基本流程如下在当前树中找到重心centroid计算经过重心的路径信息核心步骤删除重心递归处理各个连通块4. 经典应用树上路径统计以统计树上长度为 K 的路径数量为例展示点分治的实现#include bits/stdc.h using namespace std; const int N 1e5 5; vectorint g[N]; bool vis[N]; int sz[N], maxSubtree[N]; // 求子树大小和最大子树大小 void dfsSize(int u, int fa) { sz[u] 1; maxSubtree[u] 0; for (int v : g[u]) { if (v fa || vis[v]) continue; dfsSize(v, u); sz[u] sz[v]; maxSubtree[u] max(maxSubtree[u], sz[v]); } } // 找重心 int findCentroid(int u, int fa, int total) { for (int v : g[u]) { if (v fa || vis[v]) continue; if (sz[v] * 2 total) { return findCentroid(v, u, total); } } return u; } // 计算当前子树中所有节点到重心的距离 void getDistances(int u, int fa, int dist, vectorint distances) { distances.push_back(dist); for (int v : g[u]) { if (v fa || vis[v]) continue; getDistances(v, u, dist 1, distances); } } // 统计经过重心且长度为 K 的路径数量 int countPaths(int u, int K) { int res 0; vectorint allDistances; allDistances.push_back(0); // 重心自身 for (int v : g[u]) { if (vis[v]) continue; vectorint subDistances; getDistances(v, u, 1, subDistances); // 统计当前子树与之前子树的组合 for (int d : subDistances) { if (d K) { // 这里可以添加统计逻辑 } } // 合并到总距离列表 allDistances.insert(allDistances.end(), subDistances.begin(), subDistances.end()); } return res; } // 点分治主函数 int treeDivide(int u, int K) { dfsSize(u, -1); int centroid findCentroid(u, -1, sz[u]); vis[centroid] true; int ans countPaths(centroid, K); // 递归处理各个连通块 for (int v : g[centroid]) { if (vis[v]) continue; ans treeDivide(v, K); } return ans; }5. 时间复杂度分析点分治的时间复杂度通常为 O(n log n)每次找到重心后树的大小至少减半 → 递归深度 O(log n)每层需要 O(n) 时间处理所有节点总复杂度 O(n log n)实际复杂度还取决于具体问题的合并操作有时需要 O(n log² n) 或 O(n log n) 的额外数据结构。6. 常见变体与优化6.1 点分树动态点分治将每次找到的重心连接起来形成点分树支持带修改的查询操作。6.2 边分治 重构通过添加虚点将树转化为二叉树使边分治的递归深度稳定在 O(log n)。6.3 树上启发式合并DSU on Tree虽然不是严格的分治但思想类似利用重链剖分优化子树信息的合并。7. 实战例题以下是一些经典的树分治题目POJ 1741统计树上距离不超过 K 的点对数量Luogu P3806询问树上是否存在长度为 K 的路径Codeforces 321C给树节点赋值使得相邻节点值不同BZOJ 2599求树上长度为 K 的路径的最小边数8. 总结与技巧树分治的关键要点正确实现重心查找保证递归深度设计高效的信息合并方式避免重复计算注意去重防止同一路径被多次统计合理使用数据结构如数组、map、树状数组加速合并掌握树分治需要大量练习建议从模板题开始逐步挑战更复杂的问题。
树分治算法详解：从基础概念到实战应用
1. 什么是树分治树分治Tree Divide and Conquer是一种基于分治思想处理树形结构问题的算法范式。它将树分解为若干规模更小的子树分别解决子问题后再合并结果从而高效解决树上的路径统计、最值查询、动态规划等问题。2. 树分治的核心思想树分治的核心在于如何将树分而治之。主要有两种经典策略点分治每次选择树的重心作为分割点将原树分解为若干互不连通的子树保证子问题规模均衡。边分治选择一条边将树分成两个连通块递归处理两个子树。其中点分治更为常用因为它能保证递归深度为 O(log n)而边分治在菊花图中可能退化为 O(n)。3. 点分治算法框架点分治的基本流程如下在当前树中找到重心centroid计算经过重心的路径信息核心步骤删除重心递归处理各个连通块4. 经典应用树上路径统计以统计树上长度为 K 的路径数量为例展示点分治的实现#include bits/stdc.h using namespace std; const int N 1e5 5; vectorint g[N]; bool vis[N]; int sz[N], maxSubtree[N]; // 求子树大小和最大子树大小 void dfsSize(int u, int fa) { sz[u] 1; maxSubtree[u] 0; for (int v : g[u]) { if (v fa || vis[v]) continue; dfsSize(v, u); sz[u] sz[v]; maxSubtree[u] max(maxSubtree[u], sz[v]); } } // 找重心 int findCentroid(int u, int fa, int total) { for (int v : g[u]) { if (v fa || vis[v]) continue; if (sz[v] * 2 total) { return findCentroid(v, u, total); } } return u; } // 计算当前子树中所有节点到重心的距离 void getDistances(int u, int fa, int dist, vectorint distances) { distances.push_back(dist); for (int v : g[u]) { if (v fa || vis[v]) continue; getDistances(v, u, dist 1, distances); } } // 统计经过重心且长度为 K 的路径数量 int countPaths(int u, int K) { int res 0; vectorint allDistances; allDistances.push_back(0); // 重心自身 for (int v : g[u]) { if (vis[v]) continue; vectorint subDistances; getDistances(v, u, 1, subDistances); // 统计当前子树与之前子树的组合 for (int d : subDistances) { if (d K) { // 这里可以添加统计逻辑 } } // 合并到总距离列表 allDistances.insert(allDistances.end(), subDistances.begin(), subDistances.end()); } return res; } // 点分治主函数 int treeDivide(int u, int K) { dfsSize(u, -1); int centroid findCentroid(u, -1, sz[u]); vis[centroid] true; int ans countPaths(centroid, K); // 递归处理各个连通块 for (int v : g[centroid]) { if (vis[v]) continue; ans treeDivide(v, K); } return ans; }5. 时间复杂度分析点分治的时间复杂度通常为 O(n log n)每次找到重心后树的大小至少减半 → 递归深度 O(log n)每层需要 O(n) 时间处理所有节点总复杂度 O(n log n)实际复杂度还取决于具体问题的合并操作有时需要 O(n log² n) 或 O(n log n) 的额外数据结构。6. 常见变体与优化6.1 点分树动态点分治将每次找到的重心连接起来形成点分树支持带修改的查询操作。6.2 边分治 重构通过添加虚点将树转化为二叉树使边分治的递归深度稳定在 O(log n)。6.3 树上启发式合并DSU on Tree虽然不是严格的分治但思想类似利用重链剖分优化子树信息的合并。7. 实战例题以下是一些经典的树分治题目POJ 1741统计树上距离不超过 K 的点对数量Luogu P3806询问树上是否存在长度为 K 的路径Codeforces 321C给树节点赋值使得相邻节点值不同BZOJ 2599求树上长度为 K 的路径的最小边数8. 总结与技巧树分治的关键要点正确实现重心查找保证递归深度设计高效的信息合并方式避免重复计算注意去重防止同一路径被多次统计合理使用数据结构如数组、map、树状数组加速合并掌握树分治需要大量练习建议从模板题开始逐步挑战更复杂的问题。
