社区讨论

求助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 条回复,欢迎继续交流。

正在加载回复...