树形DP第一道

看这里:

#include 
      
       #define read read()using namespace std;const int N = 10000;int n,size;int head[N],a[N];int f[N][2];int read{    int x = 0,f = 1; char ch = getchar();    while( ch < 48 || ch > 57 ) {
    if(ch == '-') f = -1; ch = getchar();}    while(ch >= 48 && ch <= 57) {x = 10 * x + ch - 48; ch = getchar();}    return x * f;}struct edge{    int v,nxt;}e[N<<1];void add(int u,int v){    e[++size].v = v;    e[size].nxt = head[u];    head[u] = size;}void dfs(int u,int fa){    f[u][0] = 0; f[u][1] =  a[u];    for(int i = head[u]; i; i = e[i].nxt)    {        int v = e[i].v;        if(v == fa) continue;        dfs(v,u);        f[u][0] += max(f[v][0] , f[v][1]);        f[u][1] += f[v][0];    }}int main(){//    freopen("boos.in","r",stdin);    n = read;    for(int i = 1; i <= n; i++) a[i] = read;    int u,v;    for(int i = 1; i < n; i++)    {        v = read; u = read;        add(u,v);        add(v,u);    }    u = read; v = read;    dfs(1,0);    printf("%d",max(f[1][0] , f[1][1]));    return 0;}