社区讨论
求助GESP6级T1,玄关
学术版参与者 5已保存回复 8
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 7 条
- 当前快照
- 1 份
- 快照标识符
- @mjo3p1ro
- 此快照首次捕获于
- 2025/12/27 17:31 2 个月前
- 此快照最后确认于
- 2025/12/29 23:55 2 个月前
考场hack了两个多小时,各种诡异的树都没错,思路与同考场AC的同学一模一样,求大佬帮忙
思路:对于每个叶子节点,将其代价存入s[其父亲]中,并向上推,取s和原代价最小值,即为答案
CPP#include <bits/stdc++.h>
using namespace std;
long long n, f[100005], y[100005], c[100005], s[100005], d[100005], vis[100005], ans;
vector<int>e[100005];
void jia(int y) {
for (int w : e[y]) {
s[y] = min(d[y], s[y] + s[w]);
s[w] = 0;
}
if (y == 1) {
return ;
}
jia(f[y]);
}
int main() {
cin >> n;
f[1] = 0;
for (int i = 1; i <= n; i++) {
y[i] = 1;
}
for (int i = 2; i <= n; i++) {
cin >> f[i];
e[f[i]].push_back(i);
y[f[i]] = 0;
}
for (int i = 1; i <= n; i++) {
cin >> d[i];
}
for (int i = 1; i <= n; i++) {
if (y[i] == 1) {
c[f[i]] = 1;
}
}
for (int i = 1; i <= n; i++) {
if (y[i] == 1) {
s[i] = d[i];
}
}
for (int i = 1; i <= n; i++) {
if (y[i] == 1) {
if (!vis[f[i]]) {
jia(f[i]);
vis[f[i]] = 1;
}
}
}
cout << s[1];
return 0;
}
回复
共 8 条回复,欢迎继续交流。
正在加载回复...