洛谷P1352 没有上司的舞会

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 #define il inline
 5 #define it register int
 6 #define inf 0x3f3f3f3f
 7 #define lowbit(x) (x)&(-x)
 8 #define mem(a,b) memset(a,b,sizeof(a))
 9 #define mod 1000000007
10 const int maxn=6010;
11 struct node{
12     int to,next;
13 }a[maxn<<1];
14 int n,s,cnt,tot,head[maxn],w[maxn],vis[maxn];
15 int dp[maxn][3];
16 il void add(int u,int v){
17     a[tot].next=head[u];
18     a[tot].to=v;head[u]=tot++;
19 }
20 void dfs(int u,int fa){
21     for(it i=head[u];i!=-1;i=a[i].next){
22         it v=a[i].to;if(v==fa){continue;}
23         dfs(v,u);
24     }
25     it sum=0,sum2=0;
26     for(it i=head[u];i!=-1;i=a[i].next){
27         it v=a[i].to;if(v==fa){continue;}
28         sum+=dp[v][1];sum2+=dp[v][0];
29     }
30     dp[u][0]=sum;dp[u][1]+=sum2;
31 }
32 int main(){
33     mem(head,-1);
34     scanf("%d",&n);dp[0][0]=dp[0][1]=0;
35     for(it i=1;i<=n;i++){
36         scanf("%d",&w[i]);if(w[i]<0){w[i]=0;}
37         vis[i]=1;dp[i][1]=w[i];dp[i][0]=0;
38     }
39     for(it i=1;i<=n;i++){int v,u;
40         scanf("%d%d",&v,&u);vis[v]=0;
41         if(i==n){continue;}
42         add(v,u);add(u,v);
43     }
44     it fa=-1;
45     for(it i=1;i<=n;i++){
46         if(vis[i]){
47            fa=i;break;
48         }
49     }
50     dfs(fa,0);//cout<<fa<<endl;
51     printf("%d\n",max(dp[fa][0],dp[fa][1]));
52     return 0;
53 }