poj 2343

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<string.h>
 4 #include<vector>
 5 #include<algorithm>
 6 using namespace std;
 7 
 8 vector < int > g[6002];
 9 int w[6002],d[6002][2];
10 
11 __int64 dfs(int i,int j,int f)
12 {
13     if(d[i][j]!=-1)      //  注意要记录  不然会超时
14     {
15         return d[i][j];
16     }
17     __int64 ans=0;     //点i  不在 一定合法
18 
19     for(int k=0; k<g[i].size(); k++)
20     {
21         int v=g[i][k];
22         if(v!=f)
23             ans+=dfs(v,0,i);
24     }
25     if(j==0) //只有i 的父亲 不在i才能在
26     {
27         __int64 sum=w[i];
28         for(int k=0; k<g[i].size(); k++)
29         {
30             int v=g[i][k];
31             if(v!=f)
32                 sum+=dfs(v,1,i);
33         }
34         ans=max(ans,sum);
35     }
36     return d[i][j]=ans;
37 }
38 
39 int main()
40 {
41     int i,j,n,m,t,a,b;
42     while(scanf("%d%d",&n,&w[1])!=EOF)
43     {
44         for(i=0; i<=n; i++)
45             g[i].clear();
46         for(i=2; i<=n; i++)
47             scanf("%d",&w[i]);
48         for(i=1; ; i++)
49         {
50             scanf("%d%d",&a,&b);
51             if(a==0&&b==0)
52                 break;
53             g[a].push_back(b);
54             g[b].push_back(a);
55         }
56         memset(d,-1,sizeof(d));
57         printf("%I64d\n",dfs(1,0,-1));
58     }
59     return 0;
60 }