求助,第三个样例炸了
查看原帖
求助,第三个样例炸了
242524
JRzyh楼主2021/7/31 17:43
////////////////////////
///////////////////////
//////////////////////
/////////////////////
/////Author/////////
//////zyh//////////
//////////////////
/////////////////
////////////////
///////////////
//////////////
/////////////
////////////
#include<bits/stdc++.h>
#define EL putchar('\n')
#define SP putchar(' ')
using namespace std;
int read(){int x;scanf("%d",&x);return x;}
long long readll(){long long x;scanf("%lld",&x);return x;}
void print(int x){printf("%d",x);}
void print(long long x){printf("%lld",x);}
int n;
struct edge
{
	int to,nxt,val;
}e[100008];
int hd[100008],ecnt;
struct node
{
	int ans,w;
}a[100008];
bool cmp(node a,node b)
{
	return a.ans-a.w>b.ans-b.w;
}
void add(int u,int v,int val)
{
	e[++ecnt].to=v;
	e[ecnt].val=val;
	e[ecnt].nxt=hd[u];
	hd[u]=ecnt;
}
vector<node>tmp;
void dfs(int now)
{
	tmp.clear();
	a[now].ans=a[now].w;
	for(int i=hd[now];i;i=e[i].nxt)
	{
		dfs(e[i].to);
		tmp.push_back(a[e[i].to]);
		a[now].ans+=a[e[i].to].w;
	}
	sort(tmp.begin(),tmp.end(),cmp);
	int sum=0;
	for(int i=0;i<tmp.size();i++)
	{
		a[now].ans=max(a[now].ans,tmp[i].ans+sum);
		sum+=tmp[i].w; 
	}
	return;
}
int main()
{
	n=read();
	for(int i=2;i<=n;i++)
	{
		int p=read();
		add(p,i,0);
	}
	for(int i=1;i<=n;i++)
	{
		a[i].w=read();
	}
	dfs(1);
	for(int i=1;i<=n;i++)cout<<a[i].ans<<" ";
 	return 0;
}

2021/7/31 17:43
加载中...