北师海附Online Judge 首页 问题 来源/分类 竞赛&作业 状态 排名 常见问答
登录 注册

2251: 周年庆宴

内存限制：128 MB 时间限制：1.000 S 标准输入输出
题目类型：传统 评测方式：文本比较 上传者：
提交：1 通过：1
提交提交记录统计

题目描述

Ural大学有N个职员，编号为1~N。他们有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。每个职员有一个快乐指数。现在有个周年庆宴会，要求与会职员的快乐指数之和最大。但是，没有职员愿和直接上司一起与会。

输入格式

    第一行一个整数N。(1<=N<=6000) 
    接下来N行，第i+1行表示i号职员的快乐指数Ri。(-128<=Ri<=127) 
    接下来N-1行，每行输入一对整数L,K。表示K是L的直接上司。
    最后一行0 0表示结束。

输出格式

输出最大的快乐指数和。

输入样例 复制 

7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
0 0

输出样例 复制 

5