记录编号	33244	评测结果	AAAAAAAAAA
题目名称	火车站饭店	最终得分	100
用户昵称	fanzeyi	是否通过	通过
代码语言	C	运行时间	0.882 s
提交时间	2011-11-09 20:40:06	内存使用	39.54 MiB

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 100010

int station[MAX];
int map[MAX][100];
int f[MAX], g[MAX];
int n;

// 以 station[0] 为根.. 开始搜索.. 
// 记忆化搜索
// f[x] 为 不选此节点
// g[x] 为 选择此节点做饭店
// f[x] = sum(max(g[x], f[x])) 
// g[x] = sum(f[x])

inline int max(int a, int b) {
    return a > b ? a : b;
}

void dp(int who, int father) {
    // 先把子节点的值都算出来
    if(map[who][0] == 1 && map[who][1] == father) {
        f[who] = 0;
        g[who] = station[who];
        return;
    }
    int i;
    for(i = 1; i <= map[who][0]; i++) {
        if(map[who][i] != father) {
            dp(map[who][i], who);
        }
    }
    // 开始计算 f[x] & g[x]
    for(i = 1; i <= map[who][0]; i++) {
        if(map[who][i] != father) {
            f[who] += max(g[map[who][i]], f[map[who][i]]);
            g[who] += f[map[who][i]];
        }
    }
}

int main(int argc, char const *argv[]) {
    FILE *fin = fopen("profitz.in", "r");
    FILE *fout = fopen("profitz.out", "w");
    int i, j;
    int x, y;
    memset(map, 0, sizeof(map));
    memset(f, 0, sizeof(f));
    memset(g, 0, sizeof(g));
    fscanf(fin, "%d", &n);
    for(i = 1; i <= n; i++) {
        fscanf(fin, "%d", &station[i]);
        g[i] = station[i];
    }
    for(i = 1; i <= n - 1; i++) {
        // 读入图 邻接表 map[*][0] 存储当前有多少条边..
        fscanf(fin, "%d %d", &x, &y);
        map[x][++map[x][0]] = y;
        map[y][++map[y][0]] = x;
    }
    dp(1, 0);
    fprintf(fout, "%d\n", max(f[1], g[1]));
    return 0;
}