#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define fi first 
#define se second
const int N=5e5+10;
int c[N];
ll f[N],g[N];
struct EDGE{
	int v,nxt;
}e[N<<1]; 
int head[N],cnt;
int n;
void add(int x,int y)
{
	e[++cnt].v = y;
	e[cnt].nxt = head[x];
	head[x] = cnt;
}
bool cmp(int x,int y)
{
	return g[x]-f[x]<g[y]-f[y];
}
void dfs(int x,int fa)
{
	for(int i=head[x];i;i=e[i].nxt)
	{
		int vv=e[i].v;
		if(vv==fa) continue;
		dfs(vv,x);
		g[x]+=(g[vv]+2);
	}
	vector<int>vec;
	for(int i=head[x];i;i=e[i].nxt)
	{
		int vv=e[i].v;
		vec.push_back(vv);
	}
	f[x]=max(f[x],(ll)c[x]);
	if(vec.empty()) return;
	sort(vec.begin(),vec.end(),cmp);
	ll sum=1; 
	for(int i=1;i<=vec.size()-1;i++)
	{
		f[x]=max(f[x],f[vec[i]]+sum);
		sum+=(g[vec[i]]+2);
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&c[i]);
	}
	for(int i=1;i<=n-1;i++)
	{
		int x,y;scanf("%d%d",&x,&y);
		add(x,y);add(y,x);
	}
	dfs(1,0);
	printf("%lld\n",max(f[1],g[1]+c[1]));
	return 0;
}

这是10pts的代码（用vector存每次的子节点进行排序加更新

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define fi first 
#define se second
const int N=5e5+10;
int c[N];
ll f[N],g[N];
struct EDGE{
	int v,nxt;
}e[N<<1]; 
int head[N],cnt;
int n;
int tmp[N],tot;
void add(int x,int y)
{
	e[++cnt].v = y;
	e[cnt].nxt = head[x];
	head[x] = cnt;
}
bool cmp(int x,int y)
{
	return g[x]-f[x]<g[y]-f[y];
}
void dfs(int x,int fa)
{
	for(int i=head[x];i;i=e[i].nxt)
	{
		int vv=e[i].v;
		if(vv==fa) continue;
		dfs(vv,x);
		g[x]+=(g[vv]+2);
	}
	//vector<int>vec;
	tot=0;
	for(int i=head[x];i;i=e[i].nxt)
	{
		int vv=e[i].v;
		//vec.push_back(vv);
		tmp[++tot]=vv;
	}
	f[x]=max(f[x],(ll)c[x]);
	//if(vec.empty()) return;
	//sort(vec.begin(),vec.end(),cmp);
	sort(tmp+1,tmp+1+tot,cmp);
	ll sum=1; 
	for(int i=1;i<=tot;i++)
	{
		f[x]=max(f[x],f[tmp[i]]+sum);
		sum+=(g[tmp[i]]+2);
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&c[i]);
	}
	for(int i=1;i<=n-1;i++)
	{
		int x,y;scanf("%d%d",&x,&y);
		add(x,y);add(y,x);
	}
	dfs(1,0);
	printf("%lld\n",max(f[1],g[1]+c[1]));
	return 0;
}

这是100pts的（我把vector改成了一个全局的数组就过了

这是为什么啊？？？？？迷惑++QAQ