树的直径与相关算法实现
树的直径计算模板
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 5;
int nodeCount, startNode, distance[MAXN];
vector<int> graph[MAXN];
inline int input() {
int value = 0, sign = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') sign = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
value = (value << 3) + (value << 1) + (ch ^ 48);
ch = getchar();
}
return value * sign;
}
void traverse(int current, int parent) {
for (size_t i = 0; i < graph[current].size(); ++i) {
int neighbor = graph[current][i];
if (neighbor == parent) continue;
distance[neighbor] = distance[current] + 1;
traverse(neighbor, current);
}
}
int main() {
nodeCount = input();
for (int i = 1; i < nodeCount; ++i) {
int u = input(), v = input();
graph[u].push_back(v);
graph[v].push_back(u);
}
traverse(1, 0);
startNode = 1;
for (int i = 1; i <= nodeCount; ++i) {
if (distance[startNode] < distance[i]) startNode = i;
}
memset(distance, 0, sizeof(distance));
traverse(startNode, 0);
startNode = 1;
for (int i = 1; i <= nodeCount; ++i) {
if (distance[startNode] < distance[i]) startNode = i;
}
cout << distance[startNode];
return 0;
}
核心节点定位问题
该问题要求找出树的直径中点，并基于此进行节点评估。初始思路存在偏差，需通过树形动态规划优化解题策略。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 5;
int nodeCount, kValue, centerNode, depth[MAXN], maxDepth[MAXN];
vector<int> adjacencyList[MAXN];
inline int input() {
int value = 0, sign = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') sign = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
value = (value << 3) + (value << 1) + (ch ^ 48);
ch = getchar();
}
return value * sign;
}
void dfs(int current, int parent) {
maxDepth[current] = depth[current];
for (size_t i = 0; i < adjacencyList[current].size(); ++i) {
int neighbor = adjacencyList[current][i];
if (neighbor == parent) continue;
depth[neighbor] = depth[current] + 1;
dfs(neighbor, current);
maxDepth[current] = max(maxDepth[current], maxDepth[neighbor]);
}
}
int findMidpoint(int current) {
if (depth[current] <= (depth[centerNode] >> 1)) {
return current;
}
for (size_t i = 0; i < adjacencyList[current].size(); ++i) {
int neighbor = adjacencyList[current][i];
if (depth[neighbor] < depth[current]) {
return findMidpoint(neighbor);
}
}
return current;
}
int main() {
nodeCount = input(), kValue = input();
for (int i = 1; i < nodeCount; ++i) {
int u = input(), v = input();
adjacencyList[u].push_back(v);
adjacencyList[v].push_back(u);
}
dfs(1, 0);
centerNode = 1;
for (int i = 1; i <= nodeCount; ++i) {
if (depth[centerNode] < depth[i]) centerNode = i;
}
memset(depth, 0, sizeof(depth));
dfs(centerNode, 0);
centerNode = 1;
for (int i = 1; i <= nodeCount; ++i) {
if (depth[centerNode] < depth[i]) centerNode = i;
}
int midpoint = findMidpoint(centerNode);
memset(depth, 0, sizeof(depth));
memset(maxDepth, 0, sizeof(maxDepth));
dfs(midpoint, 0);
for (int i = 1; i <= nodeCount; ++i) {
depth[i] = maxDepth[i] - depth[i];
}
sort(depth + 1, depth + nodeCount + 1);
cout << depth[nodeCount - kValue] + 1;
return 0;
}
树网核心路径计算
本题要求找到满足特定条件的最长路径，需要特别注意边权为零的特殊情况。解题过程包含多个关键点：
- 当节点深度不超过总长度一半时，需比较当前节点与父节点的最优解
- 边权为零的场景需要额外处理，采用深度值替代距离计算
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 3e5 + 5;
int nodeCount, kValue, parent[MAXN], uplink[MAXN], degree[MAXN], depth[MAXN], distance[MAXN], maxDistance[MAXN];
struct Edge {
int target, weight;
};
vector<Edge> graph[MAXN];
inline int input() {
int value = 0, sign = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') sign = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
value = (value << 3) + (value << 1) + (ch ^ 48);
ch = getchar();
}
return value * sign;
}
void traverse(int current, int ancestor) {
maxDistance[current] = distance[current];
for (size_t i = 0; i < graph[current].size(); ++i) {
int neighbor = graph[current][i].target;
if (neighbor == ancestor) continue;
distance[neighbor] = distance[current] + graph[current][i].weight;
depth[neighbor] = depth[current] + 1;
uplink[neighbor] = graph[current][i].weight;
parent[neighbor] = current;
traverse(neighbor, current);
maxDistance[current] = max(maxDistance[current], maxDistance[neighbor]);
}
}
int findCenter(int current, int ancestor) {
if (distance[current] <= (distance[centerNode] >> 1)) {
if (max(maxDistance[current], maxDistance[current] - distance[current]) <
max(maxDistance[ancestor], maxDistance[ancestor] - distance[ancestor])) {
return current;
}
return ancestor;
}
for (size_t i = 0; i < graph[current].size(); ++i) {
int neighbor = graph[current][i].target;
if (depth[neighbor] < depth[current]) {
return findCenter(neighbor, current);
}
}
return current;
}
int main() {
nodeCount = input(), kValue = input();
for (int i = 1; i < nodeCount; ++i) {
int u = input(), v = input(), w = input();
graph[u].push_back({v, w});
graph[v].push_back({u, w});
}
traverse(1, 0);
centerNode = 1;
for (int i = 1; i <= nodeCount; ++i) {
if (distance[centerNode] < distance[i]) centerNode = i;
}
memset(distance, 0, sizeof(distance));
traverse(centerNode, 0);
centerNode = 1;
for (int i = 1; i <= nodeCount; ++i) {
if (distance[centerNode] < distance[i]) centerNode = i;
}
int center = findCenter(centerNode, 0);
memset(distance, 0, sizeof(distance));
memset(maxDistance, 0, sizeof(maxDistance));
memset(depth, 0, sizeof(depth));
memset(uplink, 0, sizeof(uplink));
memset(parent, 0, sizeof(parent));
traverse(center, 0);
for (int i = 1; i <= nodeCount; ++i) {
// 计算各节点贡献值
}
// 后续处理逻辑
return 0;
}
