全 错 这 一 快 给 我 整 自 闭
2026-08-03 17:25:39
发布于:浙江
#include <iostream>
#include <vector>
#include <string>
using namespace std;
const int MAXN = 100005;
vector<int> tree[MAXN];
int n;
string s;
int dp[MAXN]; // dp[i] 表示以 i 为根的子树中棋子的总数
void dfs(int node, int parent) {
dp[node] = s[node] - '0'; // 当前节点如果有棋子,则计数为1,否则为0
for (int child : tree[node]) {
if (child != parent) { // 避免重复遍历父节点
dfs(child, node); // 递归遍历子节点
dp[node] += dp[child]; // 累加子树中的棋子数
}
}
}
int main() {
cin >> n;
cin >> s; // 输入每个节点的初始状态,'1' 表示有棋子,'0' 表示没有棋子
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v; // 输入边信息,建立树的连接关系
tree[u].push_back(v);
tree[v].push_back(u); // 无向图,所以两边都要添加
}
// 对于每个节点,都执行一次DFS,计算以其为根的子树中的棋子总数
for (int i = 1; i <= n; ++i) {
dfs(i, 0); // 从每个节点开始DFS,计算以该节点为根的子树中的棋子总数
}
// 输出结果:每个节点作为根时的移动次数即为该节点到其子树中所有节点的棋子总数
for (int i = 1; i <= n; ++i) {
cout << dp[i] << " ";
}
cout << endl;
return 0;
}
这里空空如也

有帮助,赞一个