老程序员博客

编程生涯的最后一舞

当前位置：首页 > 技术 > 正文内容

树心分解算法详解与模板

访客 技术 2026年7月12日 2

树心分解算法详解与模板

树心分解（点分治）是一种处理树上路径问题的经典算法。其核心思想是通过递归找到树的中心（重心），将树分割成若干子树，然后分别处理跨越不同子树的路径。这种分治策略可以将复杂度从 O(n²) 优化到 O(n log n)。

算法核心步骤

  1. 寻找重心：在当前子树中找到一个节点，使得删除该节点后剩余子树的最大规模最小
  2. 处理路径：统计以重心为中介的所有路径情况
  3. 递归处理：对重心之外的子树递归执行相同操作

例题一：统计满足距离条件的节点对

给定一棵带权树，统计有多少对节点之间的距离不超过给定值 m。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 100005;
int nodeCount, limitValue;
int head[MAXN], to[MAXN << 1], nxt[MAXN << 1], edgeWeight[MAXN << 1], edgeCnt;
int tempArr[MAXN], collectArr[MAXN];
bool removed[MAXN];

void addEdge(int u, int v, int w) {
    to[++edgeCnt] = v;
    edgeWeight[edgeCnt] = w;
    nxt[edgeCnt] = head[u];
    head[u] = edgeCnt;
}

int getSize(int u, int parent) {
    if (removed[u]) return 0;
    int result = 1;
    for (int i = head[u]; i; i = nxt[i]) {
        int v = to[i];
        if (v == parent) continue;
        result += getSize(v, u);
    }
    return result;
}

int findCentroid(int u, int parent, int total, int ¢roid) {
    if (removed[u]) return 0;
    int subSize = 1, maxPart = 0;
    for (int i = head[u]; i; i = nxt[i]) {
        int v = to[i];
        if (v == parent) continue;
        int childSize = findCentroid(v, u, total, centroid);
        maxPart = max(maxPart, childSize);
        subSize += childSize;
    }
    maxPart = max(maxPart, total - subSize);
    if (maxPart <= total / 2) centroid = u;
    return subSize;
}

void collectDist(int u, int parent, int dist) {
    if (removed[u]) return;
    tempArr[++collectArr[0]] = dist;
    for (int i = head[u]; i; i = nxt[i]) {
        int v = to[i];
        if (v == parent) continue;
        collectDist(v, u, dist + edgeWeight[i]);
    }
}

int countPairs(int arr[], int len) {
    sort(arr + 1, arr + len + 1);
    int answer = 0;
    for (int i = len, j = 0; i >= 1; i--) {
        while (j + 1 < i && arr[j + 1] + arr[i] <= limitValue) j++;
        j = min(j, i - 1);
        answer += j;
    }
    return answer;
}

int solve(int u) {
    if (removed[u]) return 0;
    int result = 0, tempCnt = 0;
    findCentroid(u, -1, getSize(u, -1), u);
    removed[u] = true;
    
    for (int i = head[u]; i; i = nxt[i]) {
        int v = to[i];
        collectArr[0] = 0;
        collectDist(v, -1, edgeWeight[i]);
        result -= countPairs(tempArr, collectArr[0]);
        for (int k = 1; k <= collectArr[0]; k++) {
            if (tempArr[k] <= limitValue) result++;
            collectArr[++tempCnt] = tempArr[k];
        }
    }
    result += countPairs(collectArr, tempCnt);
    
    for (int i = head[u]; i; i = nxt[i])
        result += solve(to[i]);
    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    while (cin >> nodeCount >> limitValue, nodeCount || limitValue) {
        memset(head, 0, sizeof(head));
        memset(removed, 0, sizeof(removed));
        edgeCnt = 0;
        for (int i = 1, u, v, w; i < nodeCount; i++) {
            cin >> u >> v >> w;
            addEdge(u, v, w);
            addEdge(v, u, w);
        }
        cout << solve(0) << endl;
    }
    return 0;
}

例题二：IOI 2011 Race - 寻找最短路径

给定一棵带权树和一个目标距离 m，求包含恰好 m 长度路径的最小边数。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;
const int INF = 0x3f3f3f3f;

int nodeCount, targetDist;
int head[MAXN], to[MAXN << 1], nxt[MAXN << 1], weight[MAXN << 1], edgeCnt;
int collectArr[MAXN];
int distInfo[1000005];
int answer = INF;
pair<int, int> storeArr[MAXN], tempArr[MAXN];
bool removed[MAXN];

void addEdge(int u, int v, int w) {
    to[++edgeCnt] = v;
    weight[edgeCnt] = w;
    nxt[edgeCnt] = head[u];
    head[u] = edgeCnt;
}

int getSize(int u, int parent) {
    if (removed[u]) return 0;
    int result = 1;
    for (int i = head[u]; i; i = nxt[i]) {
        int v = to[i];
        if (v == parent) continue;
        result += getSize(v, u);
    }
    return result;
}

int findCentroid(int u, int parent, int total, int ¢roid) {
    if (removed[u]) return 0;
    int subSize = 1, maxPart = 0;
    for (int i = head[u]; i; i = nxt[i]) {
        int v = to[i];
        if (v == parent) continue;
        int childSize = findCentroid(v, u, total, centroid);
        maxPart = max(maxPart, childSize);
        subSize += childSize;
    }
    maxPart = max(maxPart, total - subSize);
    if (maxPart <= total / 2) centroid = u;
    return subSize;
}

void collectInfo(int u, int parent, int dist, int edges) {
    if (removed[u] || dist > targetDist) return;
    tempArr[++collectArr[0]] = {dist, edges};
    for (int i = head[u]; i; i = nxt[i]) {
        int v = to[i];
        if (v == parent) continue;
        collectInfo(v, u, dist + weight[i], edges + 1);
    }
}

void decompose(int u) {
    if (removed[u]) return;
    int tempCnt = 0;
    findCentroid(u, -1, getSize(u, -1), u);
    removed[u] = true;
    
    for (int i = head[u]; i; i = nxt[i]) {
        int v = to[i];
        collectArr[0] = 0;
        collectInfo(v, -1, weight[i], 1);
        
        for (int k = 1; k <= collectArr[0]; k++) {
            auto &item = tempArr[k];
            if (item.first == targetDist) 
                answer = min(answer, item.second);
            answer = min(answer, distInfo[targetDist - item.first] + item.second);
            storeArr[++tempCnt] = item;
        }
        
        for (int k = 1; k <= collectArr[0]; k++) {
            auto &item = tempArr[k];
            distInfo[item.first] = min(distInfo[item.first], item.second);
        }
    }
    
    for (int i = 1; i <= tempCnt; i++) 
        distInfo[storeArr[i].first] = INF;
    
    for (int i = head[u]; i; i = nxt[i]) 
        decompose(to[i]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> nodeCount >> targetDist;
    for (int i = 1, u, v, w; i < nodeCount; i++) {
        cin >> u >> v >> w;
        addEdge(u, v, w);
        addEdge(v, u, w);
    }
    memset(distInfo, 0x3f, sizeof(distInfo));
    decompose(0);
    cout << (answer == INF ? -1 : answer) << endl;
    return 0;
}

例题三：点分治模板 - 多查询距离存在性

给定一棵带权树和 q 个查询，对于每个查询判断是否存在两点间的距离等于该查询值。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10005;
const int MAXE = MAXN * 2;

int head[MAXN], to[MAXE], nxt[MAXE], weight[MAXE], edgeCnt;
int nodeNum, queryNum, queryVals[105];
int root, subtreeSize[MAXN], maxChild[MAXN], totalSize;
int depthArr[MAXN], distArr[MAXN], depthCnt;
bool visited[MAXN], resultArr[MAXN], existFlag[10000005];
vector<int> usedDists;

void addEdge(int u, int v, int w) {
    to[++edgeCnt] = v;
    weight[edgeCnt] = w;
    nxt[edgeCnt] = head[u];
    head[u] = edgeCnt;
}

void computeRoot(int u, int parent) {
    subtreeSize[u] = 1;
    maxChild[u] = 0;
    for (int i = head[u]; i; i = nxt[i]) {
        int v = to[i];
        if (v == parent || visited[v]) continue;
        computeRoot(v, u);
        subtreeSize[u] += subtreeSize[v];
        maxChild[u] = max(maxChild[u], subtreeSize[v]);
    }
    maxChild[u] = max(maxChild[u], totalSize - subtreeSize[u]);
    root = (maxChild[root] < maxChild[u] ? root : u);
}

void getDistances(int u, int parent) {
    depthArr[++depthCnt] = distArr[u];
    for (int i = head[u]; i; i = nxt[i]) {
        int v = to[i];
        if (v == parent || visited[v]) continue;
        distArr[v] = distArr[u] + weight[i];
        getDistances(v, u);
    }
}

void process(int center) {
    usedDists.clear();
    existFlag[0] = true;
    
    for (int i = head[center]; i; i = nxt[i]) {
        int v = to[i];
        if (visited[v]) continue;
        distArr[v] = weight[i];
        depthCnt = 0;
        getDistances(v, 0);
        
        for (int j = 1; j <= depthCnt; j++) {
            for (int k = 1; k <= queryNum; k++) {
                if (queryVals[k] < depthArr[j]) continue;
                resultArr[k] |= existFlag[queryVals[k] - depthArr[j]];
            }
        }
        
        for (int j = 1; j <= depthCnt; j++) {
            if (depthArr[j] > 1e7) continue;
            if (!existFlag[depthArr[j]]) {
                existFlag[depthArr[j]] = true;
                usedDists.push_back(depthArr[j]);
            }
        }
    }
    
    for (int i = 0; i < usedDists.size(); i++) 
        existFlag[usedDists[i]] = false;
}

void decompose(int u) {
    visited[u] = true;
    process(u);
    
    for (int i = head[u]; i; i = nxt[i]) {
        int v = to[i];
        if (visited[v]) continue;
        maxChild[root = 0] = totalSize = subtreeSize[v];
        computeRoot(v, 0);
        decompose(root);
    }
}

int main() {
    cin >> nodeNum >> queryNum;
    for (int i = 1, x, y, z; i < nodeNum; i++) {
        cin >> x >> y >> z;
        addEdge(x, y, z);
        addEdge(y, x, z);
    }
    for (int i = 1; i <= queryNum; i++) cin >> queryVals[i];
    
    maxChild[root] = totalSize = nodeNum;
    computeRoot(1, 0);
    decompose(root);
    
    for (int i = 1; i <= queryNum; i++) 
        cout << (resultArr[i] ? "AYE" : "NAY") << endl;
    
    return 0;
}

算法复杂度分析

树心分解的核心在于每次递归都将树的大小减半，因此整体时间复杂度为 O(n log n)。在处理每个重心时，需要遍历所有子树并收集距离信息，这部分通常配合排序或哈希表来实现。空间复杂度主要为 O(n)。

该算法适用于处理树上路径统计、距离查询、路径权值计算等多种问题，是竞赛中必备的知识点。

标签: 树心分解
返回列表

上一篇：Floyd算法的高级应用

下一篇：Sentry在K8S云原生环境中的JavaScript事务管理

相关文章

Linux crontab 详解

1) crontab 是什么cron 是 Linux 的定时任务守护进程；crontab 是用来编辑/查看“按时间周期执行命令”的表（cron table）。常见两类：用户 crontab：每个用户一份（crontab -e 编辑）系统级 crontab / cron.d：可指定执行用户（/etc/crontab、/etc/cron.d/*）2) crontab 时间...

富文本里可以允许的 HTML 属性

一、所有标签默认允许的安全属性（极少）class        （可选）id           （通常建议禁用）title️ 注意：id 容易被滥用做锚点注入，很多系统直接禁用class 允许的话最好只允许固定前缀（如 editor-*）二、a 标签允许属性<a href="" t...

Mac 安装 Node.js 指南

方法一：通过官网安装包（最简单，适合初学者）如果你只是想快速安装并开始使用，这是最直接的方法。访问 Node.js 官网。页面会显示两个版本：LTS (Recommended For Most Users)：长期支持版，最稳定。建议选这个。Current：最新特性版，包含最新功能但可能不够稳定。下载 .pkg 安装包并运行。按照安装向导点击“下一步”即可完成。方法二：使用 Homebrew 安装（...

Dom\HTML_NO_DEFAULT_NS 的副作用：自动加闭合标签

在使用Dom\HTMLDocument时，Dom\HTML_NO_DEFAULT_NS 将禁止在解析过程中设置元素的命名空间, 此设置是为了与DOMDocument向后兼容而存在的。当使用它时，已知的一个副作用就是：自动加闭合标签例如 </img> 为什么会这样？当你使用：Dom\HTML_NO_DEFAULT_NS文档会变成 无命名空间模式，此时内部更接近 XML...

Laravel 事件和监听器创建

在 Laravel 中，使用 Artisan 命令创建 Events（事件） 和 Listeners（监听器） 是非常高效的。你可以通过以下几种方式来实现：1. 手动创建单个 Event如果你只想创建一个事件类，可以使用 make:event 命令：Bashphp artisan make:event UserRegistered执行后，文件将生成在 app/Even...

自定义域名解析神器 dnsmasq

什么是 dnsmasq？dnsmasq 是一个轻量级、功能强大的网络服务工具，专为小型和中等规模网络设计。它是一个综合的网络基础设施解决方案[1]。dnsmasq 能做什么？功能说明应用场景DNS 转发与缓存将 DNS 查询转发到上游服务器（ISP、Google DNS 等），并在本地缓存结果加快 DNS 查询速度，减少外部 DNS 流量本地 DNS解析本地网络设备的主机名，无需编辑&n...

发表评论

访客

◎欢迎参与讨论，请在这里发表您的看法和观点。

Copyright © agingcoder.cn

Powered By Z-BlogPHP. Theme by TOYEAN.