#O1050. 树上最大权独立集

树上最大权独立集

题目描述

给定一棵 nn 个点的树,点 ii 有权值 wi>0w_i > 0。选出若干点,要求任意两个被选中的点都不相邻,求选中点权和的最大值。

题目类型

树形动态规划

输入格式

第一行一个整数 nn。

第二行 nn 个整数 wiw_i。

接下来 n−1n-1 行,每行两个整数 u,vu, v。

输出格式

一行一个整数,表示最大点权和。

样例 #1

样例输入 #1

3
10 5 7
1 2
1 3

样例输出 #1

12

数据规模与约定

数据范围 说明
1≤n≤1051 \le n \le 10^5 点数
1≤wi≤1091 \le w_i \le 10^9 点权
  • 设 fu,0/1f_{u,0/1} 表示 uu 不选/选时子树内的最大值,答案用 long long。