蒟蒻1分求助
查看原帖
蒟蒻1分求助
340632
Cry_For_theMoon楼主2020/8/21 16:33

rt

TLE+WA,除了#subtask2就没有一个点是AC的

但是我觉得思路应该没问题啊,题解也是类似的思路

求大佬帮忙看看,蟹蟹了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=5e5+10,MAXM=1e6+20;
struct Edge{
	int u,v;
}edge[MAXM];
int first[MAXN],next[MAXM],tot,size[MAXN],Limit[MAXN]; 
int ans=-1;
int a[MAXN],n,m;
long long f[MAXN][2],c[MAXN];
void addedge(int u,int v){
	tot++;
	edge[tot].u=u;edge[tot].v=v;
	next[tot]=first[u];
	first[u]=tot;
	size[u]++;
}
void dfs(int u,int fa){
	f[u][0]=f[u][1]=-1e9;
	int cnt=0;
	long long sum=0;
	for(int j=first[u];j;j=next[j]){
		int v=edge[j].v;
		if(v==fa)continue;
		dfs(v,u);
		c[++cnt]=f[v][1]-f[v][0];
		sum+=f[v][0];
	}
	if(!cnt){
		//叶子
		f[u][0]=min(a[u],a[fa]);
		if(a[u]>a[fa]){
			f[u][1]=a[u];
		}else{
			f[u][1]=-1e9;
		}
		return;
	}
	sort(c+1,c+1+cnt,greater<int>());
	for(int j=first[u];j;j=next[j]){
		int v=edge[j].v;
		if(v==fa)continue;
		//推导u - fa的边符合fa能忍受的情况
		//1. 满足fa也满足u,选min(u,fa)
		//2. 满足fa但大于u,选fa(如果在fa>u)
		//   然后u就少选一个
		
		//1.
		long long now=sum+min(a[u],a[fa]);
		for(int i=1;i<=cnt&&i<=Limit[u];i++){
			if(c[i]>=0){
				now+=c[i];
			}else break;
		}
		f[u][0]=max(f[u][0],now);
		//2.
		if(a[fa]>a[u]){
			now=sum+a[fa];
			for(int i=1;i<=cnt&&i<Limit[u];i++){
				if(c[i]>=0){
					now+=c[i];
				}else break;
			}
			f[u][0]=max(f[u][0],now);
		}
		
		//1.要么u和fa都不能忍受这条边,那就Limit-1个+m 
		//2.要么fa不能忍受但是u可以,那就Limit个+u(当a[u]>a[fa]时) 
		now=sum+m;
		for(int i=1;i<=cnt&&i<Limit[u];i++){
			if(c[i]>=0){
				now+=c[i];
			}else break;
		}
		f[u][1]=max(f[u][1],now);
		//2.
		if(a[u] > a[fa]){
			now=sum+a[u];
			for(int i=1;i<=cnt&&i<=Limit[u];i++){
				if(c[i]>=0){
					now+=c[i];
				}else break;
			}
			f[u][1]=max(f[u][1],now);
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		addedge(u,v);
		addedge(v,u);
	}
	for(int i=1;i<=n;i++){
		//size[i]-size[i]/2-1个
		Limit[i]=size[i]-(size[i]>>1)-1; 
	}
	for(int j=first[1];j;j=next[j]){
		int v=edge[j].v;
		dfs(v,1);
	} 
	//最后以1为根节点来一次贪心(选Limit个)
	int cnt=0;
	long long sum=0,now=0;
	for(int j=first[1];j;j=next[j]){
		int v=edge[j].v;
		c[++cnt]=f[v][1]-f[v][0];
		sum+=f[v][0];
	}
	sort(c+1,c+1+cnt,greater<int>()); 
	now=sum;
	for(int i=1;i<=cnt&&i<=Limit[1];i++){
		if(c[i]>=0){
			now+=c[i];
		}else break;
	}
	cout<<now<<endl;
	return 0;
}

2020/8/21 16:33
加载中...