4421. [ICPC2026河南省赛]收益

【题目描述】

给定一棵以 $1$ 号节点为根的树，树上有 $n$ 个节点，每个节点 $i$ 有一个价值为 $a_i$ 的物品，每个节点只有一个物品。树上有 $m$ 个人，第 $i$ 个人初始位于 $p_i$ 节点，不同的人可以在同一个节点。每个人可以沿着树边向深度更大的方向移动，每到达一个节点，他可以选择拿走该节点上的物品，每个物品只能被拿走一次。每个人可以移动任意步，也可以选择不移动。

所有人按照最优策略行动，求最大能拿到的物品总价值。

【输入格式】

第一行输入两个整数 $n,m$，分别表示树上点的个数和人的个数（$1 \le n,m \le 3 \times 10^5$）。

接下来 $n−1$ 行，每行两个用空格隔开的整数 $u,v$，表示 $u,v$ 之间存在一条无向边（$1 \le u,v \le n$）。

再接下来一行有 $n$ 个用空格隔开的整数 $a_1,a_2,a_3, \cdots, a_n$，$a_i$ 表示第 $i$ 个节点物品的价值（$0 \le a_i \le 10^9$）

再接下来一行有 $m$ 个用空格隔开的整数 $p_1,p_2,p_3, \cdots, p_m$，$p_i$ 表示第 $i$ 个人所在节点的编号（$1 \le p_i \le n$）。

【输出格式】

请输出一行一个数表示最大能拿到的物品总价值。

【输入样例】

6 2
1 6
5 6
6 4
1 2
2 3
2 4 6 3 1 2
1 2

【输出样例】

17

【样例说明】

第一个人从 $1$ 号节点走到 $4$ 号节点，第二个人从 $2$ 号节点走到 $3$ 号节点，每个人走到每个点都拿走所在节点的物品时获得最大总价值 $17$。

【来源】

ICPC 2026 河南省赛。

【题目描述】

给定一棵以 $1$ 号节点为根的树，树上有 $n$ 个节点，每个节点 $i$ 有一个价值为 $a_i$ 的物品，每个节点只有一个物品。树上有 $m$ 个人，第 $i$ 个人初始位于 $p_i$ 节点，不同的人可以在同一个节点。每个人可以沿着树边向深度更大的方向移动，每到达一个节点，他可以选择拿走该节点上的物品，每个物品只能被拿走一次。每个人可以移动任意步，也可以选择不移动。

所有人按照最优策略行动，求最大能拿到的物品总价值。

【输入格式】

第一行输入两个整数 $n,m$，分别表示树上点的个数和人的个数（$1 \le n,m \le 3 \times 10^5$）。

接下来 $n−1$ 行，每行两个用空格隔开的整数 $u,v$，表示 $u,v$ 之间存在一条无向边（$1 \le u,v \le n$）。

再接下来一行有 $n$ 个用空格隔开的整数 $a_1,a_2,a_3, \cdots, a_n$，$a_i$ 表示第 $i$ 个节点物品的价值（$0 \le a_i \le 10^9$）

再接下来一行有 $m$ 个用空格隔开的整数 $p_1,p_2,p_3, \cdots, p_m$，$p_i$ 表示第 $i$ 个人所在节点的编号（$1 \le p_i \le n$）。

【输出格式】

请输出一行一个数表示最大能拿到的物品总价值。

【输入样例】

6 2
1 6
5 6
6 4
1 2
2 3
2 4 6 3 1 2
1 2

【输出样例】

17

【样例说明】

第一个人从 $1$ 号节点走到 $4$ 号节点，第二个人从 $2$ 号节点走到 $3$ 号节点，每个人走到每个点都拿走所在节点的物品时获得最大总价值 $17$。

【来源】

ICPC 2026 河南省赛。