树结构算法核心技巧与典型题目解析
树的直径
树中任意两点间最长路径称为直径。求解策略：对每个节点维护其子树中到叶子的最长路径和次长路径，最终答案为所有节点的两路径之和的最大值。
int max_len[N], second_max_len[N];
int dfs(int u, int parent) {
for (auto v : graph[u]) {
if (v == parent) continue;
int len = dfs(v, u);
if (len > max_len[u]) {
second_max_len[u] = max_len[u];
max_len[u] = len;
} else if (len > second_max_len[u]) {
second_max_len[u] = len;
}
}
ans = std::max(ans, max_len[u] + second_max_len[u]);
return max_len[u] + edge_weight; // 边权
}
树的中心
到所有节点最远距离最小的点即为中心。关键性质：中心必位于从根出发的重链上。通过两次DFS预处理子树最大深度，并在第二次遍历中更新最优解。
struct MaxNode {
int child;
int dist;
};
MaxNode ml[N], sl[N];
void dfs1(int u, int p) {
for (auto v : graph[u]) {
if (v == p) continue;
dfs1(v, u);
MaxNode temp{v, ml[v].dist + w};
if (temp.dist > ml[u].dist) {
std::swap(ml[u], temp);
}
if (temp.dist > sl[u].dist) {
std::swap(sl[u], temp);
}
}
}
void dfs2(int u, int p, int up_dist) {
int current_max = std::max(ml[u].dist, up_dist);
if (current_max < min_max_dist) {
min_max_dist = current_max;
center_node = u;
}
if (up_dist > ml[u].dist) return;
for (auto v : graph[u]) {
if (v == ml[u].child) {
dfs2(v, u, std::max(sl[u].dist, up_dist) + w);
}
}
}
树的重心
使最大子树大小最小的点。可通过一次后序遍历统计子树大小并计算各节点对应的最大子树规模。
int size[N];
int best_center, min_max_subtree;
void dfs(int u, int p) {
size[u] = 1;
int max_child_size = 0;
for (auto v : graph[u]) {
if (v == p) continue;
dfs(v, u);
size[u] += size[v];
max_child_size = std::max(max_child_size, size[v]);
}
max_child_size = std::max(max_child_size, n - size[u]);
if (max_child_size < min_max_subtree) {
min_max_subtree = max_child_size;
best_center = u;
}
}
洛谷P3398：路径交集判断
给定树上两条路径，判断是否有公共点。核心结论：两路径相交当且仅当一条路径的LCA位于另一条路径上。
// LCA查询
int lca(int a, int b) {
if (deep[a] < deep[b]) std::swap(a, b);
for (int i = 20; i >= 0; --i)
if (deep[fa[a][i]] >= deep[b]) a = fa[a][i];
if (a == b) return a;
for (int i = 20; i >= 0; --i)
if (fa[a][i] != fa[b][i])
a = fa[a][i], b = fa[b][i];
return fa[a][0];
}
// 判断点是否在路径上
bool in_path(int x, int a, int b, int lca_ab) {
if (x == a || x == b || x == lca_ab) return true;
int l1 = lca(x, a), l2 = lca(x, b);
return (l1 == x && l2 == lca_ab) || (l1 == lca_ab && l2 == x);
}
// 主逻辑
if (in_path(lca_a_b, c, d, lca_c_d) || in_path(lca_c_d, a, b, lca_a_b))
puts("Y");
else
puts("N");
洛谷P4281：三点汇合点求解
求三节点到某点的总距离最小的位置。通过分析发现，答案要么是三个两两LCA中的某个，要么是其中一个唯一不同的LCA。
int la1 = lca(a, b), la2 = lca(b, c), la3 = lca(a, c);
if (la1 == la2 && la2 == la3) {
printf("%d %d\n", la1, depth[a] + depth[b] + depth[c] - 3 * depth[la1]);
} else if (la1 == la2) {
printf("%d %d\n", la3, abs(depth[la3] - depth[a]) + abs(depth[la3] - depth[c]) +
abs(depth[la1] - depth[la3]) + abs(depth[la1] - depth[b]));
} else if (la2 == la3) {
// 同理处理
} else {
// 处理其他情况
}
洛谷P5588：同色路径计数
统计每种颜色下长度大于1且包含该颜色所有出现点的路径数量。关键思想：识别"极低点"（子树中无同色点的最低点）。
- 若只有一个极低点：所有同色点构成链，路径数由最高点决定。
- 若有且仅有两个极低点：若最高点不在两点路径上，则路径数为两子树大小乘积。
- 超过两个极低点：无合法路径。
void dfs2(int u, int p) {
ll old_cnt = cnt[color[u]];
for (auto v : graph[u]) {
if (v == p) continue;
dfs2(v, u);
}
if (cnt[color[u]] == old_cnt) {
low_points[color[u]].push_back(u);
}
++cnt[color[u]];
}
洛谷P5536：核心城市选址
选k个点作为核心，使得非核心点到最近核心点的最大距离最小。贪心策略：先选直径中点，再依次选择能覆盖最远区域的点。
void dfs1(int u, int p) {
mv[u] = 1;
for (auto v : graph[u]) {
if (v == p) continue;
dfs1(v, u);
mv[u] = std::max(mv[u], mv[v] + 1);
update_max(u, v, mv[v]);
}
}
void dfs2(int u, int up) {
int max_depth = ml[u].dist > up ? ml[u].dist : up;
if (max_depth < best_dist) {
best_dist = max_depth;
center = u;
}
if (ml[u].dist <= up) return;
dfs2(ml[u].child, std::max(up + 1, sl[u].dist + 1));
}
// 使用优先队列扩展覆盖范围
priority_queue<Node> pq;
pq.push({center, depth_from_center});
while (k--) {
auto top = pq.top(); pq.pop();
for (auto neighbor : graph[top.node]) {
if (!visited[neighbor]) pq.push({neighbor, new_depth});
}
}
洛谷P1273：有线电视网收益最大化
树形分组背包问题：选取若干叶节点，目标为（收益和）减去（路径代价和）≥0 的前提下最大化数量。
const int INF = -1e9;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
dp[i][j] = INF;
// 叶子节点初始化
for (int i = n - m + 1; i <= n; ++i)
dp[i][1] = value[i], siz[i] = 1;
// 后序遍历更新
void dfs(int u, int p) {
for (auto [v, w] : graph[u]) {
if (v == p) continue;
dfs(v, u);
for (int i = siz[u]; i >= 0; --i)
for (int k = 0; k <= siz[v] && k <= i; ++k)
dp[u][i] = std::max(dp[u][i], dp[u][i - k] + dp[v][k] - w);
}
}
HDU6035：彩色路径颜色种类总和
求所有路径上不同颜色数量之和。转换思路：对每种颜色，计算不经过它的路径数，再用总数减去。
ll total_pairs = n * (n - 1) / 2;
ll ans = 0;
void dfs(ll u, ll p) {
ll old_sum = sum[col[u]];
for (auto v : graph[u]) {
if (v == p) continue;
dfs(v, u);
ll new_sum = sum[col[u]];
ll delta = new_sum - old_sum;
ll remaining = siz[v] - delta;
ans += remaining * (remaining - 1) / 2;
sum[col[u]] += remaining;
}
sum[col[u]]++;
}
// 最终结果
ans = total_pairs * n - ans;
