树形结构核心算法：遍历序、直径与重心
深度优先遍历序列
深度优先遍历序列（简称DFS序）通过记录节点首次和末次被访问的时间戳，将树形结构转化为线性区间。对于节点u，设其首次访问序号为in[u]，末次访问序号为out[u]，则以u为根的子树操作可转化为对区间[in[u], out[u]]的操作。
实现方式：在DFS过程中维护全局计时器，进入节点时记录in值，离开前记录out值。
int timer = 0;
void dfs(int u, int parent) {
in[u] = ++timer;
for (int v : adj[u]) {
if (v == parent) continue;
dfs(v, u);
}
out[u] = timer;
}
树的最长路径（直径）
定义：树中任意两节点间的最长简单路径称为直径。求解方法有两种：
方法一：双次遍历法
任选一节点出发，找到距离最远的节点x；再从x出发，找到最远的节点y。路径x-y即为直径。
vector<int> adj[N];
int depth[N], parent[N];
int farthestNode = 0, maxDepth = 0;
void traverse(int u, int p) {
parent[u] = p;
if (depth[u] > maxDepth) {
maxDepth = depth[u];
farthestNode = u;
}
for (int v : adj[u]) {
if (v == p) continue;
depth[v] = depth[u] + 1;
traverse(v, u);
}
}
int findDiameter(int start) {
memset(depth, 0, sizeof(depth));
maxDepth = 0;
traverse(start, 0);
int x = farthestNode;
memset(depth, 0, sizeof(depth));
maxDepth = 0;
traverse(x, 0);
return maxDepth;
}
优势：可还原路径；劣势：无法处理负权边。
方法二：动态规划法
对每个节点，计算其到子节点的最长和次长路径，直径即为所有节点（最长+次长）的最大值。
int maxLen[N], secLen[N], result = 0;
void dp(int u, int p) {
for (int v : adj[u]) {
if (v == p) continue;
dp(v, u);
int path = maxLen[v] + weight(u, v);
if (path > maxLen[u]) {
secLen[u] = maxLen[u];
maxLen[u] = path;
} else if (path > secLen[u]) {
secLen[u] = path;
}
}
result = max(result, maxLen[u] + secLen[u]);
}
优势：支持负权边；劣势：无法直接获取路径节点。
树的重心
定义：使删除该节点后最大子树尺寸最小的节点称为重心。
性质：
- 删除重心后，各连通块尺寸尽可能均衡
- 所有节点到重心的距离总和最小
- 增删一个节点，重心最多移动一个位置
- 连接两棵树时，新重心位于原重心路径上
求解算法
通过DFS计算各子树大小，并维护最大子树尺寸的最小值。
int subtreeSize[N], minMaxSubtree = INF;
int calculateSize(int u, int p) {
subtreeSize[u] = 1;
int maxSubtree = 0;
for (int v : adj[u]) {
if (v == p) continue;
int childSize = calculateSize(v, u);
subtreeSize[u] += childSize;
maxSubtree = max(maxSubtree, childSize);
}
maxSubtree = max(maxSubtree, totalNodes - subtreeSize[u]);
minMaxSubtree = min(minMaxSubtree, maxSubtree);
return subtreeSize[u];
}
实践应用
案例一：带权树直径（支持负权）
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 40005;
struct Edge { int to, w; };
vector<Edge> g[MAXN];
long long best[MAXN], second[MAXN], answer = -1e18;
void solve(int u, int parent) {
for (auto e : g[u]) {
if (e.to == parent) continue;
solve(e.to, u);
long long candidate = best[e.to] + e.w;
if (candidate > best[u]) {
second[u] = best[u];
best[u] = candidate;
} else if (candidate > second[u]) {
second[u] = candidate;
}
}
answer = max(answer, best[u] + second[u]);
}
int main() {
int n; scanf("%d", &n);
for (int i = 1; i < n; i++) {
int a, b, c; scanf("%d%d%d", &a, &b, &c);
g[a].push_back({b, c});
g[b].push_back({a, c});
}
solve(1, 0);
printf("%lld", answer);
return 0;
}
案例二：重心定位
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
vector<int> tree[MAXN];
int n, sz[MAXN], optimal = INT_MAX;
int dfs(int u, int p) {
sz[u] = 1;
int worst = 0;
for (int v : tree[u]) {
if (v == p) continue;
int child = dfs(v, u);
sz[u] += child;
worst = max(worst, child);
}
worst = max(worst, n - sz[u]);
optimal = min(optimal, worst);
return sz[u];
}
int main() {
scanf("%d", &n);
for (int i = 1; i < n; i++) {
int x, y; scanf("%d%d", &x, &y);
tree[x].push_back(y);
tree[y].push_back(x);
}
for (int i = 1; i <= n; i++) sz[i] = 1;
dfs(1, 0);
printf("%d", optimal);
return 0;
}
案例三：路径核心查询
给定带权树和限制长度S，在直径上选取连续段使其长度不超过S，最小化所有节点到该段的最大距离。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 400;
long long dist[MAXN][MAXN], pathNodes[MAXN];
int n, limit, pathCount = 0;
bool onDiameter[MAXN];
void floydWarshall() {
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
void extractPath(int start, int end) {
// 通过父节点数组还原路径
}
int main() {
scanf("%d%d", &n, &limit);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
dist[i][j] = (i == j) ? 0 : 1e9;
for (int i = 1; i < n; i++) {
int u, v, w; scanf("%d%d%d", &u, &v, &w);
dist[u][v] = dist[v][u] = w;
}
floydWarshall();
// 寻找直径端点
int x = 1, y = 1;
long long maxDist = 0;
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
if (dist[i][j] < 1e9 && dist[i][j] > maxDist) {
maxDist = dist[i][j];
x = i; y = j;
}
// 提取直径路径到pathNodes
// 双指针滑动窗口求解
return 0;
}
案例四：高效路径核心（线性复杂度）
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 400020;
struct Edge { int to, next, w; };
Edge edges[MAXN];
int head[MAXN], parent[MAXN], path[MAXN];
long long prefix[MAXN], far[MAXN];
bool mark[MAXN];
int n, edgeCnt = 0, pathLen = 0;
void addEdge(int u, int v, int w) {
edges[++edgeCnt] = {v, head[u], w};
head[u] = edgeCnt;
}
void findEndpoint(int u, int p, long long depth, int& farthest) {
if (depth > prefix[0]) {
prefix[0] = depth;
farthest = u;
}
for (int i = head[u]; i; i = edges[i].next) {
int v = edges[i].to;
if (v == p) continue;
findEndpoint(v, u, depth + edges[i].w, farthest);
}
}
void tracePath(int u, int p) {
parent[u] = p;
for (int i = head[u]; i; i = edges[i].next) {
int v = edges[i].to;
if (v == p) continue;
tracePath(v, u);
}
}
long long computeFar(int u, int p, long long acc) {
if (mark[u]) acc = 0;
long long res = acc;
for (int i = head[u]; i; i = edges[i].next) {
int v = edges[i].to;
if (v == p) continue;
res = max(res, computeFar(v, u, acc + edges[i].w));
}
far[u] = max(far[u], res);
return mark[u] ? 0 : res;
}
int main() {
int S; scanf("%d%d", &n, &S);
for (int i = 1; i < n; i++) {
int a, b, c; scanf("%d%d%d", &a, &b, &c);
addEdge(a, b, c); addEdge(b, a, c);
}
int x = 1, y = 1;
prefix[0] = 0; findEndpoint(1, 0, 0, x);
prefix[0] = 0; findEndpoint(x, 0, 0, y);
tracePath(y, 0);
for (int cur = x; cur; cur = parent[cur]) {
path[++pathLen] = cur;
mark[cur] = true;
}
computeFar(y, 0, 0);
// 双指针优化处理
return 0;
}
案例五：巡逻路线规划
在树中添加K条边（K≤2）使总巡逻距离最短。添加边可减少往返路径，但需保证每条边至少访问一次。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200020;
struct Edge { int to, next, w; };
Edge e[MAXN];
int h[MAXN], n, K, edgeCnt = 0;
int parent[MAXN];
long long down[MAXN], up[MAXN], total = 0;
void addEdge(int u, int v, int w) {
e[++edgeCnt] = {v, h[u], w};
h[u] = edgeCnt;
}
void dfs1(int u, int p) {
for (int i = h[u]; i; i = e[i].next) {
int v = e[i].to;
if (v == p) continue;
dfs1(v, u);
long long cand = down[v] + e[i].w;
if (cand > down[u]) {
up[u] = down[u];
down[u] = cand;
} else if (cand > up[u]) {
up[u] = cand;
}
}
total = max(total, down[u] + up[u]);
}
void dfs2(int u, int p, long long dist) {
if (dist > total) {
total = dist;
parent[0] = u;
}
for (int i = h[u]; i; i = e[i].next) {
int v = e[i].to;
if (v == p) continue;
dfs2(v, u, dist + e[i].w);
}
}
int main() {
scanf("%d%d", &n, &K);
for (int i = 1; i < n; i++) {
int a, b; scanf("%d%d", &a, &b);
addEdge(a, b, 1); addEdge(b, a, 1);
}
if (K == 1) {
dfs1(1, 0);
printf("%lld\n", 2LL * (n - 1) - total);
} else {
// 第一次找直径并标记
total = 0; dfs2(1, 0, 0);
int start = parent[0];
total = 0; dfs2(start, 0, 0);
int end = parent[0];
// 修改直径边权为-1
// 第二次DP求新直径
total = 0; dfs1(1, 0);
printf("%lld\n", 2LL * (n - 1) - total);
}
return 0;
}
