#P14051. 【深度优先搜索7】小塔的奇妙树
-
ID: 2148
Tried: 623
Accepted: 165
Difficulty: 5
【深度优先搜索7】小塔的奇妙树
本题为2024年9月8日字节跳动机考原题
字节跳动机考的介绍点击这里
题目内容
小塔有一棵n个点的树，其中1号点是根。每个点有一个权值ai。如果满足任意节点的权值大于等于其子节点的权值和，那么这棵树就是一棵奇妙树。 小塔每次操作可以选择一个点，将其权值加一。请问小塔最少需要多少次操作，才能使这棵树变成一棵奇妙树。
输入描述
第一行一个整数n，表示树的节点数。
第二行n 个整数ai;，表示每个点的权值。
接下来n−1行，每行两个整数u和v，表示u和v之间有一条边。
2≤n≤105
1≤ai≤109
1≤u,v≤n
输出描述
输出一个整数，表示最少需要多少次操作。
样例1
输入
3
1 2 3
1 2
1 3
输出
4
说明
至少需要4次操作，将1号点的权值变为5.
【深度优先搜索7】小塔的奇妙树
题目简述
小塔有一棵包含 n 个点的树，树的根为 1 号点。每个点有一个权值，树是奇妙树的定义是：任意节点的权值都要大于等于其子节点权值之和。我们的目标是，通过对树中的节点执行最少的加一操作，使得这棵树变成一棵奇妙树。
解题思路
1. 奇妙树的要求
对于每一个节点 u，若该节点有多个子节点 v1,v2,...,vk，则要求：
如果不满足这个条件，我们需要增加该节点的权值，直到满足条件为止。
2. 贪心与DFS
为了尽可能的减少操作次数，我们使用贪心的思想，从底向上操作（DFS 先访问子节点，再对父节点操作）。
-
DFS遍历：我们从根节点开始，依次遍历树的每个节点。对于每个节点
u，我们需要处理它的子树。 -
子树权值和的计算：当遍历到某个节点时，
先遍历其子节点，计算每个子节点的权值和，然后根据奇妙树的条件来调整当前节点的权值。如果当前节点的权值小于子节点的权值和，那么我们需要将当前节点的权值增加到子节点权值和之上。 -
操作计数：每次调整节点的权值时，需要记录调整的次数，这个就是我们所要求的最少操作次数。
3. 时间复杂度
- 因为我们是使用 DFS 遍历树，时间复杂度是
O(n)。 - 对于每个节点，我们仅仅需要计算其所有子节点的权值和，并进行一次比较，整体复杂度为线性。
因此，整体时间复杂度为 O(n)，这对于最大规模105 是可以接受的。
代码实现
Python
import sys
sys.setrecursionlimit(200000)
def dfs(node, father, adj, a):
total_add = 0
total_sum = 0 # 记录子树的总权值和
# 处理所有子节点
for neighbor in adj[node]:
if neighbor != father:
child_add, child_sum = dfs(neighbor, node, adj, a)
total_add += child_add
total_sum += child_sum
# 确保当前节点的权值大于等于所有子节点的权值和
if a[node] < total_sum:
total_add += total_sum - a[node]
a[node] = total_sum # 将当前节点的权值增加到子节点权值和
# 返回当前节点需要增加的操作次数和当前节点的总权值
return total_add, a[node]
def solve(n, a, edges):
# 构建树的邻接表
adj = [[] for _ in range(n)]
for u, v in edges:
adj[u-1].append(v-1)
adj[v-1].append(u-1)
# 初始化
result, _ = dfs(0, -1, adj, a) # 从根节点0开始DFS
return result
# 输入部分
n = int(input()) # 节点数
a = list(map(int, input().split())) # 权值数组
edges = [tuple(map(int, input().split())) for _ in range(n-1)] # 边的输入
# 调用函数并输出结果
print(solve(n, a, edges))
Java 代码实现
import java.util.*;
public class Main {
static Long totalAdd = 0L;
static Long dfs(int node, int father, List<Integer>[] adj, Long[] a) {
Long totalSum = 0L;
// 处理所有子节点
for (int child : adj[node]) {
if (child != father) {
totalSum += dfs(child, node, adj, a);
}
}
// 确保当前节点的权值大于等于所有子节点的权值和
if (a[node] < totalSum) {
totalAdd += totalSum - a[node]; // 更新全局的totalAdd
a[node] = totalSum; // 更新当前节点的权值
}
return a[node];
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 节点数
Long[] a = new Long[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextLong(); // 权值数组
}
int[][] edges = new int[n - 1][2];
for (int i = 0; i < n - 1; i++) {
edges[i][0] = sc.nextInt();
edges[i][1] = sc.nextInt();
}
List<Integer>[] adj = new ArrayList[n];
for (int i = 0; i < n; i++) {
adj[i] = new ArrayList<>();
}
// 构建树的邻接表
for (int[] edge : edges) {
adj[edge[0] - 1].add(edge[1] - 1);
adj[edge[1] - 1].add(edge[0] - 1);
}
// 从根节点0开始DFS
dfs(0, -1, adj, a);
System.out.println(totalAdd); // 输出最终的totalAdd
}
}
C++ 代码实现
#include <iostream>
#include <vector>
using namespace std;
#define ll long long
pair<ll, ll> dfs(int node, int father, const vector<vector<int>>& adj, vector<ll>& a) {
ll totalAdd = 0;
ll totalSum = 0;
// 处理所有子节点
for (int child : adj[node]) {
if (child != father) {
auto result = dfs(child, node, adj, a);
totalAdd += result.first;
totalSum += result.second;
}
}
// 确保当前节点的权值大于等于所有子节点的权值和
if (a[node] < totalSum) {
totalAdd += totalSum - a[node];
a[node] = totalSum; // 更新当前节点的权值
}
return {totalAdd, a[node]};
}
int main() {
int n;
cin >> n;
vector<ll> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<pair<int, int>> edges(n - 1);
for (int i = 0; i < n - 1; i++) {
cin >> edges[i].first >> edges[i].second;
}
vector<vector<int>> adj(n);
// 构建树的邻接表
for (const auto& edge : edges) {
adj[edge.first - 1].push_back(edge.second - 1);
adj[edge.second - 1].push_back(edge.first - 1);
}
vector<bool> visited(n, false);
auto result = dfs(0, -1, adj, a); // 从根节点0开始DFS
cout << result.first << endl;
return 0;
}