#O1050. 树上最大权独立集
树上最大权独立集
题目描述
给定一棵 个点的树,点 有权值 。选出若干点,要求任意两个被选中的点都不相邻,求选中点权和的最大值。
题目类型
树形动态规划
输入格式
第一行一个整数 。
第二行 个整数 。
接下来 行,每行两个整数 。
输出格式
一行一个整数,表示最大点权和。
样例 #1
样例输入 #1
3
10 5 7
1 2
1 3
样例输出 #1
12
数据规模与约定
| 数据范围 | 说明 |
|---|---|
| 点数 | |
| 点权 |
- 设 表示 不选/选时子树内的最大值,答案用
long long。