又是WA又是RE,蒟蒻卑微求助
查看原帖
又是WA又是RE,蒟蒻卑微求助
318165
xzavierchan楼主2020/8/16 14:34

不知道错在哪了。。。

#include<iostream>
#include<string.h>
using namespace std;
//链式前向星 
struct Edge{
	int to,next;
};
Edge edge[16010];
int head[16010];
void add(int u,int v){//加边 
	edge[cnt].to=v;
	edge[cnt].next=head[u];
	head[u]=cnt++;
}

int n;//节点个数 
int nums[16010];//每个节点的权重 
int dp[16010];//dp[i]:存放 i为根的联通区最大值 
int cnt=0;//边的条数 
bool visit[16010];//避免dfs的时候重复遍历,造成死循环
 

int ans=-2147483647;

void dfs(int root){//遍历 
	if(head[root]==-1) 	dp[root]=nums[root];
	else{
		visit[root]=true;
		dp[root]=nums[root];
		for(int i=head[root];i!=-1;i=edge[i].next){
			if(visit[edge[i].to]==true) continue;
			else{
				dfs(edge[i].to);
				dp[root]+=max(0,dp[edge[i].to]);
			}
		}
		ans=max(ans,dp[root]);
	}
	
}

int main(){
	memset(head,-1,sizeof(head));
	memset(visit,false,sizeof(visit));
	cin>>n;
	for(int i=1;i<=n;i++) cin>>nums[i];
	int l,k;
	for(int i=1;i<n;i++){
		cin>>l>>k;
		add(l,k);
		add(k,l);//双重加边 
	}
	dfs(1);
	cout<<ans;
	return 0;
} 
2020/8/16 14:34
加载中...