Posted on 2008-09-28 10:05
superman 閱讀(181)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
URAL
1 /* Accepted 0.109 457 KB */
2 #include <iostream>
3
4 using namespace std;
5
6 int n;
7 int s[6000];
8 int p[6000];
9
10 int f[6000][2];
11
12 void search(int i)
13 {
14 int SonCnt = 0;
15 for(int k = 0; k < n; k++)
16 if(p[k] == i)
17 {
18 search(k);
19 SonCnt++;
20 }
21
22 if(SonCnt == 0)
23 {
24 f[i][0] = 0; f[i][1] = s[i];
25 return;
26 }
27
28 f[i][1] = s[i];
29 for(int k = 0; k < n; k++)
30 if(p[k] == i)
31 {
32 f[i][0] += max(f[k][0], f[k][1]);
33 f[i][1] += f[k][0];
34 }
35 }
36
37 int main()
38 {
39 memset(p, 255, sizeof(p));
40
41 scanf("%d", &n);
42 for(int i = 0; i < n; i++)
43 scanf("%d", s + i);
44 while(true)
45 {
46 int s, t;
47 scanf("%d %d", &s, &t);
48 if(s == 0 && t == 0)
49 break;
50 p[s - 1] = t - 1;
51 }
52
53 int root;
54 for(int i = 0; i < n; i++)
55 if(p[i] == -1)
56 {
57 root = i; break;
58 }
59
60 search(root);
61
62 cout << max(f[root][0], f[root][1]) << endl;
63
64 return 0;
65 }
66