社区讨论

麻烦DALAO帮忙看看快读哪里写错了

P1352没有上司的舞会参与者 4已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@lo8bb561
此快照首次捕获于
2023/10/27 15:49
2 年前
此快照最后确认于
2023/10/27 15:49
2 年前
查看原帖
CPP
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
inline int read(){
	int w=1,s=0;
	char ch=getchar();
	while(ch>'9'||ch<'0'){	w=-1;ch=getchar();}
	while(ch<='9'&&ch>='0'){	s=s*10+ch-'0';ch=getchar();}
	return s*w;
}
const int N=6e3+1; //这里要+1不然TLE 
int n,head[N],cnt=0;

struct ahaha{
	int to,next,w;
}t[N];
void add(int u,int v,int w){
	cnt++;
	t[cnt].w=w;
	t[cnt].to=v;
	t[cnt].next=head[u];
	head[u]=cnt;
}
int f[N][4];
void dfs(int u){
	f[u][1]=t[u].w;
	for(int i=head[u];i;i=t[i].next){
		int v=t[i].to;
		if(u==v)	return;
		dfs(v);
		f[u][0]+=max(f[v][1],f[v][0]);
		f[u][1]+=f[v][0];
	}
}

bool st[N];
int main(){
//	std::ios::sync_with_stdio(false);
	n=read();
	for(int i=1;i<=n;i++){
		t[i].w=read();
	}
	for(int i=1;i<=n-1;i++){
		int  u,v;
		v=read();
		u=read();
		add(u,v,t[i].w);
		st[v]=true;
	}
	int root=1;
	while(st[root])	root++;
//	cout<<root<<endl;
	dfs(root);
	cout<<max(f[root][1],f[root][0]);
	return 0;
}


回复

3 条回复,欢迎继续交流。

正在加载回复...