树形dp

#include <bits/stdc++.h>
using namespace std;
const int maxn=200000;
int f[maxn][2],w[maxn],head[maxn];
int cnt;
bool vis[maxn];
inline int read(){
int num=0,f=1; char c=getchar();
while(!isdigit(c)){
if(c=='-') f=-1; c=getchar();
}
while(isdigit(c)){
num=(num+(num<<2)<<1)+(c^48); c=getchar();
}
return num*f;
}
struct node{
int end,next;
}e[maxn];
inline void add_edge(int,int);
void dfs(int);
inline void add_edge(int a,int b){
e[++cnt].end=b;
e[cnt].next=head[a];
head[a]=cnt;
//
cout<<a<<" "<<head[a]<<endl;
//
cout<<e[cnt].next<<" "<<endl;

}
void dfs(int u){
int v;
vis[u]=1;
for(int i=head[u];i!=0;i=e[i].next){
v=e[i].end; //cout<<vis[v]<<" "; cout<<endl<<endl;
if(vis[v]==1) continue;
dfs(v);
f[u][0]+=f[v][1];
f[u][1]+=max(f[v][0],f[v][1]);
}
f[u][0]+=w[u];
//cout<<f[u][0]<<" ";
//cout<<endl<<endl;
return;
}
int main(){
freopen("profitz.in","r",stdin);
freopen("profitz.out","w",stdout);
int n,a,b;
n=read();
for(int i=1;i<=n;i++){
w[i]=read();
}
for(int i=1;i<n;i++){
a=read(); b=read();
add_edge(a,b);
add_edge(b,a);
}
//
for(int i=1;i<=cnt;i++){
//
//
cout<<e[i].next<<" "<<endl;
//
}

dfs(1);
/*
for(int i=1;i<=n;i++){
cout<<f[i][0]<<" "<<f[i][1];
cout<<endl;
}
*/
int ans=max(f[1][1],f[1][0]);
cout<<ans;
return 0;
}
cogs.pro 火车站饭店