全 错 这 一 快 给 我 整 自 闭
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;
}
全部评论 1
#include <bits/stdc++.h>
using namespace std;typedef long long ll;
const int MAXN = 500005;int n, m;
char s[MAXN];
vector<int> g[MAXN];// ---------- 第一遍：以 1 为根，求子树棋子数 a[] ----------
int pa[MAXN];
ll subTok[MAXN]; // 子树棋子数
ll dep[MAXN]; // 到根1的距离
ll sumTokDep[MAXN]; // 该子树内棋子到根1的距离和void dfs1(int u, int p) {
pa[u] = p;
subTok[u] = (s[u] == '1');
sumTokDep[u] = 0;
for (int v : g[u]) if (v != p) {
dep[v] = dep[u] + 1;
dfs1(v, u);
subTok[u] += subTok[v];
sumTokDep[u] += sumTokDep[v] + subTok[v] * 1; // 边权=1
}
}// ---------- 定根时计算该根答案（贪心压缩） ----------
// b[v] = v 子树内最终被占用点数；用 slack = a[v] - b[v] 模型。
// 从根 BFS：选根后，逐层把节点加入；可选当且仅当沿祖先链 slack 均>0。
// 返回 (ans)
ll solveRoot(int root) {
// 重新定根：计算 a[v]（当前 root 下的子树棋子数）与 dep2[v]
// 为换根效率，这里用"增量"；下面给的是逻辑实现，正式版用并查式 Euler。
static vector<int> order;
order.clear();
vector<int> par(n + 1, 0);
vector<ll> a(n + 1, 0), d(n + 1, 0);
function<void(int, int)> dfs = [&](int u, int p) {
par[u] = p; a[u] = (s[u] == '1'); order.push_back(u);
for (int v : g[u]) if (v != p) {
d[v] = d[u] + 1; dfs(v, u); a[u] += a[v];
}
};
dfs(root, 0);// slack[v] = a[v] - (当前已选在 v 子树内的点数) vector<ll> slack = a; // BFS 选点 vector<char> inT(n + 1, 0); queue<int> q; int picked = 0; auto tryPick = [&](int w) -> bool { // 检查 w 及其所有祖先 slack > 0 int x = w; while (x != 0) { if (slack[x] <= 0) return false; x = par[x]; } // 实际选 w：沿祖先链 slack-- x = w; while (x != 0) { slack[x]--; x = par[x]; } inT[w] = 1; picked++; return true; }; // 根必选 if (m > 0) { int x = root; while (x != 0) { slack[x]--; x = par[x]; } inT[root] = 1; picked = 1; } // frontier：根的孩子 for (int v : g[root]) if (v != par[root]) q.push(v); while (!q.empty() && picked < m)2026-10-18 来自 广东
0
有帮助，赞一个