1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| const int MAX=6000+10;
int n,ish[MAX],vis[MAX],l,k,rt,f[MAX][2];
struct Edge{
int to,next;
}e[MAX];
int tot,h[MAX];
void init(){
tot=0;
mem(h,-1);
}
void addedge(int u,int v){
e[tot].to=v;
e[tot].next=h[u];
h[u]=tot++;
}
void dfs(int u){
vis[u]=1;
for(int i=h[u];i!=-1;i=e[i].next){
int v=e[i].to;
if(!vis[v]){
dfs(v);
f[u][0] += max(f[v][0],f[v][1]);
f[u][1] += f[v][0];
}
}
}
int main(){
freopen("in","r",stdin);
sf(n);
init();
mem(vis,0);
mem(ish,0);
fi(i,1,n+1)
sf(f[i][1]);
rt=1;
fi(i,1,n+1){
sf(l);sf(k);
addedge(k,l);
if(ish[l]) rt=k;
ish[l]=ish[k]=1;
}
dfs(rt);
pf(max(f[rt][0],f[rt][1]));
return 0;
}
|