AcWing
  • 首页
  • 题库
  • 题解
  • 分享
  • 问答
  • 活动
  • 应用
  • 吐槽
  • 登录/注册

AcWing 285. 没有上司的舞会

作者: 作者的头像   p_c ,  2019-08-11 14:01:20 ,  阅读 63


0


#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int maxn = 6005;

int n;
int happy[maxn];
int h[maxn], e[maxn], ne[maxn], idx;
bool has_father[maxn];
int f[maxn][2];

inline void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

inline void dfs(int u) {
    f[u][1] = happy[u];

    for(int i = h[u]; i + 1; i = ne[i]) {
        int v = e[i];
        dfs(v);
        f[u][0] += max(f[v][1], f[v][0]);
        f[u][1] += f[v][0];
    }
}

int main(void) {
    scanf("%d", &n);
    memset(h, -1, sizeof h);

    for(int i = 1; i <= n; i ++) scanf("%d", &happy[i]);

    for(int i = 1; i <= n - 1; i ++) {
        int a, b; scanf("%d%d", &a, &b);
        add(b, a);
        has_father[a] = true;
    }

    int root = 1;
    while(has_father[root]) root++;

    dfs(root);

    printf("%d\n", max(f[root][1], f[root][0]));
    return 0;
}

0 评论

你确定删除吗?

© 2018-2020 AcWing 版权所有  |  京ICP备17053197号-1
联系我们  |  常见问题
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息