0pts,人已死
查看原帖
0pts,人已死
594755
niweizheni楼主2024/7/11 21:02

我为什么全wa???????

#include<bits/stdc++.h>
using namespace std;

const int N=2e5+15;
unsigned long long n,k,m,r,p,root;

unsigned long long h[N*2],to[N*2],ne[2*N],idx=1;
unsigned long long a[N*2],aid[N*2];//初始值 
unsigned long long sum[N*4],lazy[N*4],ll[N*4],rr[N*4];//线段树数组(和,懒标记) 
unsigned long long son[N*2],id[N*2],fa[N*2],cnt=0,dep[N*2],ssize[N*2],top[N*2],sizetip=0; 
//son表示他的重儿子,id表示他的编号,fa表示他的父亲节点,cnt是编号记录器,dep是他的深度,ssize是他儿子加上他自己的大小,top是他重链的顶端
unsigned long long ans=0,res=0,w[N*2];//答案 
unsigned long long sson=0;//答案 

void add(int u,int v)//链式前向星 
{
	to[idx]=v;
	ne[idx]=h[u];
	h[u]=idx++;
} 

bool cmp(unsigned long long x,unsigned long long y)
{
	return x>y;
}

void dfs(int u,int f,int deep)
{
	dep[u]=deep;
	fa[u]=f;
	ssize[u]=a[u];
	int maxson=0;
	for(int i=h[u];i!=-1;i=ne[i]) 
	{
		int v=to[i];
		if(v==f)
		{
			continue;
		}
		dfs(v,u,deep+1);
		
		if(ssize[v]>maxson)
		{
			son[u]=v;
			maxson=ssize[v];
		}
	}
	ssize[u]+=maxson;
}

void dp_dfs(int u,int topf)
{
	top[u]=topf;
	if(!son[u])
	{
		return;
	}
	dp_dfs(son[u],topf);
	for(int i=h[u];i!=-1;i=ne[i])
	{
		int v=to[i];
		if(v==fa[u]||v==son[u])
		{
			continue;
		}
		dp_dfs(v,v);
	}
}


int main()
{
	memset(h,-1,sizeof(h));
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		sson+=i;
	}
	for(int i=1;i<n;i++)
	{
		int x,y;
		cin>>x>>y;
		add(x,y);
		add(y,x);
		sson-=y;
	}
	root=sson;
	dfs(root,0,1);
	dp_dfs(root,root);
	sort(w+1,w+sizetip+1,cmp);
	for(int i=1;i<=n;i++)
	{
		if(i==top[i])
		{
			++sizetip;
			w[sizetip]=ssize[i];
		}
	}
	//cout<<sizetip<<endl;
	for(int i=1;i<=k;i++)
	{
	//	cout<<w[i]<<endl;
		ans+=w[i];
	}
	cout<<ans;
	return 0;
}
2024/7/11 21:02
加载中...