树的直径——树形 D P 、两次 B F S \Huge{树的直径——树形DP、两次BFS} 树的直径——树形DP、两次BFS
不再详细解释代码,只记录完整模板。
树形DP
可以计算负权边。
时间复杂度: O ( n ) O(n) O(n)。
设 D [ x ] D[x] D[x]表示从节点 x x x出发走向以 x x x为根的字数,能够到达的最远节点的距离;设 y i y_i yi表示子节点, e d g e ( x , y ) edge(x,y) edge(x,y)表示边权,则有:
D [ x ] = m a x 1 ≤ i ≤ t ( D [ y i ] + e d g e ( x i , y i ) ) D[x]=max_{1\le i\le t}(D[y_i]+edge(x_i,y_i)) D[x]=max1≤i≤t(D[yi]+edge(xi,yi))
设F[x]为经过节点x的最长链长度,则有:
F [ x ] = m a x 1 ≤ j < i ≤ t ( D [ y i ] + D [ y j ] + e d g e ( x , y i ) + e d g e ( x , y j ) ) F[x]=max_{1\le j<i\le t}(D[y_i]+D[y_j]+edge(x,y_i)+edge(x,y_j)) F[x]=max1≤j<i≤t(D[yi]+D[yj]+edge(x,yi)+edge(x,yj))
int res, n, b[N], d[N];
vector<PII> a[N];
void dp(int x) {
b[x] = 1;
for(int i = 0; i < a[x].size(); i ++ ) {
int t = a[x][i].fi, u = a[x][i].se;
if(b[t]) continue;
dp(t);
res = max(res, d[x] + d[t] + u);
d[x] = max(d[x], d[t] + u);
}
}
void Solved() {
cin >> n;
for (int i = 0; i < n - 1; ++i) {
int x, y, z; cin >> x >> y >> z;
a[x - 1].push_back({y - 1, z});
a[y - 1].push_back({x - 1, z});
}
dp(0);
cout << res << endl;
}
两次BFS
实现最长直径长度,计算出直径上的具体节点。
无法计算负权边!!!
时间复杂度: O ( n ) O(n) O(n)。
struct Node {int id, distance;};// 结点
struct Edge {int to, weight;}; // 边
vector<vector<Edge>> tree; //用于存储树的结构
vector<bool> visited; //标记
vector<int> parent; //存放父节点
Node bfs(int start) {// 第一次 BFS,从任意结点开始找到最远的结点
queue<Node> q;
visited.assign(tree.size(), false);
q.push({start, 0});
visited[start] = true;
Node farthest = {start, 0};
while (!q.empty()) {
Node current = q.front(); q.pop();
if (current.distance > farthest.distance) farthest = current;
for (const Edge& edge : tree[current.id]) {
if (!visited[edge.to]) {
visited[edge.to] = true;
q.push({edge.to, current.distance + edge.weight});
parent[edge.to] = current.id; // 保存父节点信息
}
}
}
return farthest;
}
vector<int> diameter() {// 第二次 BFS,从最远的结点开始找到直径的另一端
Node start = bfs(0);
Node end = bfs(start.id);
vector<int> path;
path.push_back(end.id);
// 从 end.id 向上回溯到 start.id,得到直径上的所有节点
int current = end.id;
while (current != start.id) {
current = parent[current]; // 根据父节点数组回溯
path.push_back(current);
}
reverse(path.begin(), path.end());
path.push_back(end.distance); //将最长直径一并返回
return path;
}
int main() {
int n; cin >> n;
tree.resize(n); parent.resize(n, -1);
for (int i = 0; i < n - 1; ++i) {
int x, y, z; cin >> x >> y >> z;
tree[x - 1].push_back({y - 1, z});
tree[y - 1].push_back({x - 1, z});
}
vector<int> path = diameter();
cout << path.back() << endl; //输出最长直径
path.pop_back(); //将答案删除
for (int node : path) //输出最长直径具体节点
cout << node + 1 << " ";
return 0;
}