ID: 2508

Difficulty: 8

所属公司 : 阿里

时间 :2025年4月19日-阿里淘天(算法岗)

算法标签>

树形dp

题目内容

小红拿到一棵节点总数为 $n$ 的树，编号为 $1$ ~ $n$ ，保证 $n$ 为奇数。

其中每个点的点权为 $a_i$ ，附属代价为 $b_i$ 。

题解

题目描述

小红拿到一棵节点总数为 $n$ 的树，编号为 $1$ ~ $n$ ，保证 $n$ 为奇数。

其中每个点的点权为 $a_i$ ，附属代价为 $b_i$ 。

每次操作，小红可以选择一个树上的连通块，再选择连通块中的一个节点，将其点权 $+1$ 或者 $-1$ ，代价为连通块中所有节点的附属代价之和。