社区讨论
麻烦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 条回复,欢迎继续交流。
正在加载回复...