第三个样例不过,10分,过了前两个点
查看原帖
第三个样例不过,10分,过了前两个点
365532
Mr_ll楼主2022/11/10 09:42
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1e5+10;
int n,hea[N<<1],pa,net[N<<1],cnt,to[N<<1],a[N],ans[N];
int read() {
	int x=0;char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x;
}
void add(int x,int y) {
	to[++cnt]=y;
	net[cnt]=hea[x];
	hea[x]=cnt;
}
struct node {
	int ans,a;
}nd[N];
bool cmp(node i,node j) {
	if(max(i.ans,i.a+j.ans)==max(j.ans,j.a+i.ans)) return i.a<j.a;
	return max(i.ans-i.a,i.a+j.ans)<max(j.ans,j.a+i.ans);
}
void dfs(int x,int fa) {
	int tot=0;
	for(int i=hea[x];i;i=net[i]) {
		int y=to[i];
		if(y==fa) continue;
		dfs(y,x);
		nd[++tot].a=a[y];
		nd[tot].ans=ans[y];
	}
	if(!tot) {
		ans[x]=a[x];
		return;
	}
	sort(nd+1,nd+1+tot,cmp);
	int sum=0;
	for(int i=1;i<=tot;i++) {
		ans[x]=max(ans[x],sum+nd[i].ans);
		sum+=nd[i].a;
	}
	ans[x]=max(ans[x],sum+a[x]);
	return;
}
int main() {
	n=read();
	for(int i=2;i<=n;i++) {
		pa=read();
		add(i,pa);
		add(pa,i);
	}
	for(int i=1;i<=n;i++) a[i]=read();
	dfs(1,0);
	for(int i=1;i<=n;i++) printf("%d ",ans[i]);
	return 0;
} 
2022/11/10 09:42
加载中...