大佬们求助,为什么这段代码只能做对一半,我感觉逻辑没问题啊
#include<iostream>
#include<vector>
using namespace std;
int n; // 节点数量
vector<vector<int>> map; // 邻接表
vector<int> subTree; // 子树节点数量
vector<bool> visited; // 访问标记数组
vector<int> dp; // 动态规划数组
int minDistanceSum; // 最小距离和
int targetNode; // 目标节点
// 计算子树大小的DFS函数
void countSubTree(int node) {
visited[node] = true;
for (int i : map[node]) {
if (!visited[i]) {
countSubTree(i);
subTree[node] += subTree[i];
}
}
}
// 计算从根节点到所有节点距离和的DFS函数
void countDistances(int node, int distance) {
visited[node] = true;
dp[1] += distance;
for (int i : map[node]) {
if (!visited[i]) {
countDistances(i, distance + 1);
}
}
}
// 计算每个节点的距离和并更新最小距离和的节点
void solve(int node) {
visited[node] = true;
for (int i : map[node]) {
if (!visited[i]) {
dp[i] = dp[node] + n - 2 * subTree[i];
if (dp[i] < minDistanceSum) {
targetNode = i;
minDistanceSum = dp[i];
}
solve(i); // 递归调用solve
}
}
}
int main() {
cin >> n;
map.resize(n + 1);
subTree.resize(n + 1, 1);
visited.resize(n + 1, false);
dp.resize(n + 1);
// 读取输入,构建树的邻接表
for (int i = 1; i < n; i++) {
int a, b;
cin >> a >> b;
map[a].push_back(b);
map[b].push_back(a);
}
// 计算子树大小
countSubTree(1);
// 重置访问标记数组
fill(visited.begin(), visited.end(), false);
// 计算从根节点到所有节点的距离和
countDistances(1, 0);
// 初始化最小距离和和目标节点
minDistanceSum = dp[1];
targetNode = 1;
// 重置访问标记数组
fill(visited.begin(), visited.end(), false);
// 计算每个节点的距离和并更新最小距离和的节点
solve(1);
// 输出目标节点和最小距离和
cout << targetNode << " " << minDistanceSum;
return 0;
}