7000: 【树形DP】字节跳动2024秋招-小M的奇妙树
金币值：
1
时间限制：4.000 s
内存限制：128 M
正确：11
提交：24
正确率：45.83% 命题人：
题目描述
小M有一棵包含$n$个节点的树，其中编号为1的节点是根节点。每个节点都有一个权值$a_i$。如果树中任意节点的权值都大于或等于其所有子节点权值的总和，这棵树被认为是一棵奇妙树。小M可以通过对任意节点执行加一操作来增加其权值。请问，小M最少需要进行多少次操作才能使这棵树变成一棵奇妙树？
输入格式
首先输入一个整数$n$，表示树的节点数。
接下来一行输入$n$个整数$a_i$，表示每个节点的权值。
随后的$n-1$行，每行两个整数$u$和$v$，表示节点$u$和$v$之间存在一条边。
- $2 \leq n \leq 10^5$
- $1 \leq a_i \leq 10^5$
- $1 \leq u, v \leq n$
接下来一行输入$n$个整数$a_i$，表示每个节点的权值。
随后的$n-1$行，每行两个整数$u$和$v$，表示节点$u$和$v$之间存在一条边。
- $2 \leq n \leq 10^5$
- $1 \leq a_i \leq 10^5$
- $1 \leq u, v \leq n$
输出格式
输出一个整数，表示小M为使树成为奇妙树所需进行的最小操作次数。
输入样例 复制
3
1 2 3
1 2
1 3输出样例 复制
4