求助大佬用邻接表建树咋写
查看原帖
求助大佬用邻接表建树咋写
473710
hmr26108楼主2023/8/2 21:58

我这样写有什么问题吗

#include<bits/stdc++.h>
#define maxn 100010
using namespace std;
int tot,h[maxn],d[maxn],cnt,vis[maxn];
int n,w[maxn];
struct node
{
	int v,next;
}e[maxn];
int cmp(node a,node b)
{
	return d[a.v]-w[a.v]>d[b.v]-w[b.v];
}
void add(int u,int v)
{
	tot++;
	e[tot].v=v;
	e[tot].next=h[u];
	h[u]=tot;
}
void dfs(int u)
{
	vis[u]=1;
	int cur=cnt;
	for(int i=h[u];i;i=e[i].next)
	{
		int v=e[i].v;
		if(vis[v]) continue;
		cnt++;
		dfs(v);
		d[u]+=w[v];
	}
	sort(e+1+cur,e+cnt+1,cmp);
	int sum=0;
	for(int i=h[u];i;i=e[i].next)
	{
		//printf("%d %d\n",u,e[i].v);
		d[u]=max(d[u],d[e[i].v]+sum);
		sum+=w[e[i].v];
		//printf("%d %d\n",u,sum);
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n-1;i++)
	{
		int v;
		scanf("%d",&v);
		add(v,i+1);
	}
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&w[i]);
		d[i]=w[i];
	}
	dfs(1);
	for(int i=1;i<=n;i++)
	{
		printf("%d ",d[i]);
	}
	return 0;
}
2023/8/2 21:58
加载中...