@[Firrel](/user/530570) 这是dp题，不是搜索，卡你时间空间的
by liverxiwo @ 2024-04-25 13:25:13
@[liverxiwo](/user/1162380) 再看一眼，dfs只是用于查找深度的
by Firrel @ 2024-04-25 13:28:55
w 数组太大了，用很多没用的空间，建议用 vector 数组
by Tomle @ 2024-04-26 10:08:26
这样
```cpp
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<vector>
using namespace std;
struct node{
int nxt,to;
}mp[6001];
int n,start,de,st,topp;
int r[6001],dp[6001],tot[6001],head[6001];
bool coo[6001],vis[6001];
vector <int> w[6001];
void add(int u,int v){
mp[++topp].to = v,mp[topp].nxt = head[u];
head[u] = topp;
return ;
}
void dfs(int now,int dep){
//printf("%d\n",now);
de = max(de,dep);
w[dep].push_back(now);
for(int i = head[now];i;i = mp[i].nxt){
//if(!vis[mp[i].to]){
//vis[mp[i].to] = 1;
dfs(mp[i].to,dep + 1);
//}
}
return ;
}
int main(){
scanf("%d",&n);
for(int i = 1;i <= n;i++) scanf("%d",&r[i]);
for(int i = 1;i < n;i++){
int l,k;
scanf("%d%d",&l,&k);
add(k,l);
vis[l] = 1;
}
for(int i = 1;i <= n;i++){
if(!vis[i]){
st = i;
break;
}
}
//printf("%d\n",st);
dfs(st,1);
for(int i = de;i >= 1;i--){
for(int j = 0;j < w[i].size();j++){
int now = w[i][j],cnt = 0,m = 0;
dp[now] = r[now];
for(int k = head[now];k;k = mp[k].nxt){
if(!coo[mp[k].to]) m += dp[mp[k].to];
cnt += dp[mp[k].to];
}
if(dp[now] + m > cnt){
dp[now] = dp[now] + m;
coo[now] = 1;
}
else if(cnt >= 0) dp[now] = cnt;
//printf("i : %d,j : %d\n",i,j);
//printf("%d:%d\n",now,dp[now]);
}
}
printf("%d",dp[st]);
return 0;
}
```
by Tomle @ 2024-04-26 10:12:52
@[Tomle](/user/942161) 膜拜中朋友
by Firrel @ 2024-04-26 12:44:19