題目見ural1039
1: #include <stdio.h>
2: #include <stdlib.h>
3: #include <iostream>
4: #define maxn 6010
5: using namespace std;
6:
7: struct ss
8: {
9: int ro,nu;
10: } a[maxn];
11: int w[maxn];
12: int f[maxn][2];
13: int n;
14: int x,y;
15: int t[maxn];
16:
17: int cmp(const void*a,const void*b)
18: {
19: ss c=*(ss*)a,d=*(ss*)b;
20: if (c.ro<d.ro) return -1;
21: if (c.ro>d.ro) return 1;
22: return 0;
23: }
24:
25: void dp(int x)
26: {
27: if (f[x][1]) return;
28: for (int i=t[x];i<t[x+1];++i)
29: {
30: int k=a[i].nu;
31: dp(k);
32: f[x][1]+=f[k][0];
33: f[x][0]+=max(f[k][0],f[k][1]);
34: }
35: f[x][1]+=w[x];
36: }
37:
38: int main()
39: {
40: freopen("party.in","r",stdin);
41: freopen("party.out","w",stdout);
42:
43: scanf("%d",&n);
44: for (int i=1;i<=n;++i) scanf("%d",&w[i]);
45: scanf("%d%d",&x,&y);
46: while (!((!x)&&(!y)))
47: {
48: a[x].nu=x;
49: a[x].ro=y;
50: scanf("%d%d",&x,&y);
51: }
52: for (int i=1;i<=n;++i)
53: if (!a[i].ro)
54: a[i].nu=i;
55: a[0].ro=-1;
56: qsort(a,n+1,sizeof(ss),cmp);
57: for (int i=1;i<=n;++i)
58: if (!t[a[i].ro])
59: t[a[i].ro]=i;
60: t[n+1]=n+1;
61: for (int i=n;i>0;--i)
62: if (!t[i])
63: t[i]=t[i+1];
64: dp(0);
65: printf("%d\n",max(f[0][1],f[0][0]));
66: return 0;
67: }
68: